Program of the Workshop

Descriptional Complexity

of Automata, Grammars and Related Structures

Tuesday, July 20, 1999
09:30-09:45 Opening
09:45-10:45 Invited Lecture: J. Gruska (Brno):
Quantum Challenges for Descriptional Complexity
10:45-11:10 Coffee Break
11:10-11:55 Invited Lecture: H. Petersen (Stuttgart):
Prefix Rewriting and Descriptional Complexity
11:55-14:00 Lunch
14:00-15:00 Invited Lecture: H. Leung (Las Cruces):
Tight Lower Bounds on the Size of Sweeping Automata
15:00-15:30 M. Kappes (Frankfurt am Main):
Descriptional Complexity of Finite Automata with Multiple Initial States
15:30-15:55 Coffee Break
15:55-16:25 Y. Velinov (Scottsville):
Regions of Influence in Simple Decomposition Form of Finite Functions
16:25-16:55 C. Martin-Vide (Tarragona), A. Mateescu (Turku):
Special Families of Sewing Languages
16:55-17:15 Break
17:15-18:15 Open Problem Session

Wednesday, July 21, 1999
09:00-10:00 Invited Lecture: S. Yu (London, Ontario):
State Complexity of Regular Languages
10:00-10:25 Coffee Break
10:25-10:55 C. Mereghetti, G. Pighizzini (Milan):
Unary Automata Simulations and Cyclic Languages
10:55-11:25 H. Schmitz (Würzburg):
Generalized Deterministic Languages and their Automata: A Characterization of Restricted Temporal Logic
11:25-11:55 A.N. Trahtman (Ramat Gan):
Computing the Order of Local Testability
11:55-14:00 Lunch
14:00- Excursion to Federal Garden Show

Thursday, July 22, 1999
09:00-10:00 Invited Lecture: J.O. Shallit (Waterloo, Ontario):
10:00-10:25 Coffee Break
10:25-10:55 A. Paun (London, Ontario):
On the Diameter of Various Classes of H Systems
10:55-11:25 N.G. David, K.G. Subramanian, D.G. Thomas (Madras):
On Descriptional Measures of a Class of Graph Grammars
11:25-11:55 A. Ito, K. Inoue, Y. Wang (Tokiwadai, Ube):
Alternating Automata Characterizations of One-Way Iterative Arrays
11:55-14:00 Lunch
14:00-14:45 Invited Lecture: K. Hashiguchi (Tsushima, Okayama):
Formal Languages over Free Binoids
14:45-15:15 J.M. Sempere (Valencia):
Linear Expressions
15:15-15:45 S. Crespi Reghizzi, M. Pradella, P. San Pietro (Milan):
Conciseness of Associative Language Descriptions
15:45-16:10 Coffee Break
16:10-17:40 Business Meeting of IFIP Working Group 1.2 Descriptional Complexity
18:30- Banquet

Friday, July 23, 1999
09:00-10:00 Invited Lecture: A. Kelemenová (Opava):
Complexity Aspects in Colonies and Eco-Grammar Systems
10:00-10:25 Coffee Break
10:25-11:10 Invited Lecture: E. Csuhaj-Varjú (Budapest):
Grammar Systems with Bounded Resources -- On Size Complexity of Grammar Systems
11:10-11:40 V. Mitrana (Bucharest):
On the Degree of Communication in Parallel Communicating Finite Automata Systems
11:40-12:10 C.S. Calude (Auckland):
A Characterization of C.E. Random Reals

DCAGRS '99 Homepage

Bernd Reichel, Magdeburg 05.06.99