|
Graph
Drawing and Information Visualization |
|
As graphs are known to be one of
the most important abstract models in various scientific and engineering
areas, graph drawing (or information visualization in a broader sense) has
naturally emerged as a fast growing research topic in computer science. Our
research focuses on algorithmic aspects of graph drawing, including
-
designing algorithms for drawing a wide class of graphs
meeting certain aesthetic criteria,
-
analyzing complexities of various graph drawing problems,
-
applying graph drawing techniques to real-world
applications including VLSI floor-planning, boundary labeling,
visualization of hierarchical structures, text annotations, ... and more.
Selected publications:
-
C. Lin, H. Yen, and J. Chuang,
Drawing Graphs with Nonuniform
Nodes Using Potential Fields, accepted for publication in
Journal of Visual Languages and Computing, April, 2009. (Preliminary
version presented at GD 2003)
-
C. Lin, H. Kao, and H. Yen, Many-to-One Boundary
Labeling, Journal of Graph Algorithms and Applications, (special
issue for APVIS 2007), Vol. 13, No. 3, pp. 319-356, 2008.
-
C. Lin and H. Yen, On Balloon Drawings of Rooted Trees,
Journal of Graph Algorithms and Applications, (special issue for GD
2005), Vol. 11, No. 2, pp. 431-452, 2007.
-
J. Fan, C. Lin, H. Lu, and H.Yen, Width-Optimal
Visibility Representation of Plane Graphs, in Proc. of the 18th
International Symposium on Algorithms and Computation (ISAAC
2007), (LNCS 4835), pp. 160-171, Sendai, Japan, Dec. 17-19,
2007.
|
 |
|
Membrane
Computing |
Membrane computing (MC) identifies an unconventional
computing model from natural phenomena of cell evolutions and
chemical reactions. MC has a great potential for implementing massively
parallel systems in an efficient way that would allow us to solve
currently intractable problems once future bio-technology (or
silicon-technology) gives way to a practical bio-realization (or
chip-realization). In our study,
we investigate various computational issues related to
MC, establishing the following results:
-
•nonuniversality
of deterministic catalytic systems
-
•model-checking
of signaling membrane systems
-
•identifying
computational power of membrane systems w.r.t. various notions of
parallelism...
Selected publications:
-
O.
Ibarra, and H. Yen, Deterministic Catalytic Systems Are not Universal,
Theoretical Computer Science 363(2): 149-161, 2006.
-
O.
Ibarra, S. Woodworth, H. Yen, and Z. Dang, On the Computational Power
of 1-Deterministic and Sequential P Systems, Fundamenta Informaticae,
Vol. 73 (1-2), pp. 133-152, 2006.
-
C.
Li, Z. Dang, O. Ibarra, and H. Yen, Signaling P Systems and
Verification Problems, in Proc. of the
32nd International Colloquium on Automata, Languages and
Programming (ICALP'05),
(LNCS 3580), pp. 1462-1473, July 11-15, 2005, Lisboa, Portugal. ,
-
O.
Ibarra, H. Yen, and Z. Dang, On Various Notions of Parallelism in P
Systems, International Journal of Foundations of Computer Science,
Vol. 16, No. 4, pp. 683-706, August 2005.
|
 |
|
Petri Net Theory |
|
Petri nets, introduced by C. A Petri in 1962, provide an
elegant and useful mathematical formalism for modelling concurrent systems and
their behaviors. In many applications, however, modelling by itself is of
limited practical use if one cannot analyze the modelled system. As a means of
gaining a better understanding of the Petri net model, the decidability and
computational complexity of typical automata theoretic problems concerning
Petri nets have been extensively investigated in the literature in the past
four decades. Our research on Petri nets focuses on decidability/complexity
analysis of various problems associated with Petri nets (equivalently,
vector addition systems, vector replacement systems, and vector addition
systems with states).
Selected publications:
-
H. Yen,
Path Decomposition and Semilinearity of Petri Nets, International Journal of
Foundations of Computer Science, Vol. 20, No. 4, 581-596, 2009.
-
H. Yen and C.
Chen, On Minimal Elements of Upward-closed Sets,
Theoretical Computer Science, Vol.
410, 2442-2452, 2009.
-
H. Yen, On Reachability
Equivalence for BPP Nets, Theoretical
Computer Science Vol. 179, No. 1-2, pp. 397-419, June 1997.
-
R.
Howell, L. Rosier, and H. Yen,
Normal and Sinkless Petri Nets, Journal of
Computer and System Sciences, Vol. 46, pp. 1-26, February 1993.
-
R.
Howell, L. Rosier and H. Yen, A
Taxonomy of Fairness and Temporal Logic Problems for Petri Nets,
Theoretical Computer Science, Vol. 82,
1991, pp. 341-372.
|
|
|
Supervisory Control of Discrete Event Systems |
|
Following the work of Ramadge and Wonham (1989), the study
of control theory in discrete event dynamic systems has benefited a great deal
from the knowledge of automata theory, formal languages, and Petri
net theory. Our interests along this line of research include investigating
various problems concerning discrete event systems from an algorithmic
viewpoint.
Selected publications:
-
H. Yen,
Decidability and Complexity Analysis of Forbidden State Problems for
Discrete Event Systems, International Journal of Foundations of Computer
Science, Vol. 19, No. 4, 999-1013, 2008.
-
H. Yen
and L. Yu, Decidability Analysis of Self-Stabilization for Infinite State
Systems, Fundamenta Informaticae, Vol. 70,
No. 4, 387-402, 2006.
-
H. Yen, Sequential versus
Concurrent Languages of Labeled Conflict-Free Petri Nets,
IEEE Trans. on Automatic Control, Vol.
47, No. 7, pp. 1158-1162, July 2002.
-
H. Yen, A Valuation-Based Analysis
of Conflict-Free Petri Nets, Systems and
Control Letters, Vo. 45, No. 5, pp. 387 - 395, 2002.
-
H. Yen, Fair Control of
Omega-Automata, in the Proceedings of the 5th
International Workshop on Discrete Event Systems (WODES 2000)
(published in a book `Discrete Event Systems:
Analysis and Control' by Kluwer Academic Publishers), pp. 355-362,
Ghent, Belgium, August 21-23, 2000.
|
 |
|
Additional
Research Interests |
|
I am also interested in the following topics:
|
 
|
