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