Programme
Monday, July 16
18:00 Registration at Hotel Erzherzog Rainer, Wiedner Hauptstrasse 27-29
Tuesday, July 17
9:15 Opening of DLT 2001
Session 1: Discrete Structures I
9:30 Invited Lecture:
Permutations, and Representations of Numbers
H. Prodinger (Johannesburg, South Africa)
10:20 The Power of One-Letter Rational Languages
T. Cachat (Aachen, Germany)
10:45 The Entropy of Lukasiewicz-Languages
L. Staiger (Halle, Germany)
11.10 Break
Session 2: Synchronized Automata
11:40 Collapsing Words vs. Synchronizing Words
D. S. Ananichev, M. V. Volkov (Ekaterinburg, Russia)
12:05 A Note on Synchronized Automata and Road Coloring Problem
K. Culik II (Columbia, USA), J.Karhumäki, J. Kari (Turku, Finland)
12:30 Lunch
Session 3: Algebraic Methods
14:15 Invited Lecture:
The Equational Theory of Fixed Points with Applications to Generalized Languages
Z.Ésik (Szeged, Hungary)
15:05 Shuffle Quotient and Decompositions
C. Câmpeanu, K. Salomaa (Kingston, Canada), S. Vágvölgyi (Szeged, Hungary)
15.30 Break
Session 4: Language Families I
16:00 Invited Lecture:
Some Petri Net Languages and Codes
M. Ito (Kyoto, Japan), Y. Kunimoch (Fukuroi, Japan)
16:50 The Growing Context-Sensitive Languages are the Acyclic Context-Sensitive Languages
G. Niemann (Kassel, Germany), J. R. Woinowski (Darmstadt, Germany)
17:15 End of Session
20:00 Reception in the Rathaus
Wednesday, July 18
Session 5: Logical Definability
9:05 Invited Lecture:
Complexity of Second-Order Logic over Finite Structures
G. Gottlob (Wien, Austria)
9:55 Recognizable Sets of N-free Pomsets are Monadically Axiomatizable
D. Kuske (Leicester, United Kingdom)
10:20 Automata on Series-Parallel Biposets
Z. Ésik, Z. L. Németh (Szeged, Hungary)
10:45 Break
Session 6: Language Hierarchies
11:15 Hierarchies of String Languages Generated by Deterministic Tree Transducers
J. Engelfriet, S. Maneth (Leiden, The Netherlands)
11:40 Partially-Ordered Two-Way Automata: A New Characterization of DA
T. Schwentick (Jena, Germany), D. Thérien (Montréal, Canada), H. Vollmer (Würzburg, Germany)
12:05 Level 5/2 of the Straubing-Thérien Hierarchy for Two-Letter Alphabets
Ch. Glaßer (Würzburg, Germany), H. Schmitz (München, Germany)
12:30 Lunch
Session 7: Randomness
14:15 Invited Lecture:
Automata: From Uncertainty to Quantum
C. S. Calude, E. Calude (Auckland, New Zealand)
15:05 On the Power of Randomized Pushdown Automata
J. Hromkovic (Aachen, Germany), G. Schnitger (Frankfurt am Main, Germany)
15:30 Break
Session 8: Discrete Structures II
16:00 Invited Lecture:
Decision Questions on Integer Matrices
T. Harju (Turku, Finland)
16:50 The Root of a Language and its Complexity
G. Lischke (Jena, Germany)
17:15 End of Session
18:00 Sightseeing in Wien
Thursday, July 19
Session 9: Proof Theory
9:05 Invited Lecture:
Some Elementary Theories of Ordinals
Ch. Choffrut (Paris, France)
9:55 Invited Lecture:
Complexity of Propositional Proofs
A. Razborov (Moskwa, Russia)
10:45 Break
Session 10: Generalized Grammars
11:15 Valuated and Valence Grammars: An Algebraic View
H. Fernau (Tübingen, Germany), R. Stiebe (Halle, Germany)
11:40 Context-Free Valence Grammars - Revisited
H. J. Hoogeboom (Leiden, The Netherlands)
12:05 Lunch
14:00 Bus Trip to the Wienerwald and Heuriger in Mödling
Friday, July 20
Session 11: Universal Machines
9:05 Invited Lecture:
Some Perspectives of Infinite Automata Theory
W. Thomas (Aachen, Germany)
9:55 An Undecidability Result Concerning Periodic Morphisms
V. Halava, T. Harju (Turku, Finland)
10:20 A New Small Universal Turing Machine
Y.Rogozhin (Chisinau, Moldova), M. Kudlek (Hamburg, Germany)
10:45 Break
Session 12: Language Families II
11:15 Minimal Covers of Formal Languages
M. Domaratzki, J. Shallit (Waterloo, Canada), S. Yu (London, Canada)
11:40 Some Regular Languages that are Church-Rosser Congruential
G. Niemann (Kassel, Germany), J. Waldmann (Leipzig, Germany)
12.05 On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy
M. Beaudry (Sherbrooke, Canada), M. Holzer (München, Germany), G. Niemann, F. Otto (Kassel, Germany)
12:30 Lunch
Session 13: Patterns
14:15 Invited Lecture:
Words and Patterns
A. Restivo, S. Salemi (Palermo, Italy)
15:05 Forbidden Factors and Fragment Assembly
F. Mignosi, A. Restivo, M. Sciortino (Palermo, Italy)
15:30 Break
Session 14: Grammar Systems
16:00 Parallel Communicating Grammar Systems with Incomplete Information Communication
E. Csuhaj-Varjú, G. Vaszil (Budapest, Hungary)
16:25 Eliminating Communication by Parallel Rewriting
B. Rovan, M.Slast'an (Bratislava, Slovakia)
16:50 String Rewriting Sequential P-Systems and Regulated Rewriting
P. Sosík (Opava, Czech Republic), R. Freund (Wien, Austria)
17:15 End of Session
18:00 Reception by the Rektor of Technische Universität Wien
End of DLT 2001
Saturday, July 21 and Sunday, July 22
Descriptional Complexity of Automata, Grammars and Related Structures 2001 (DCAGRS 2001)
Homepage DLT2001
Last update: June, 6th 2000, 23:00 (MS)
pagemaster