12. DLT 2008: Kyoto, Japan

Invited Talks

• Zoltán Ésik:
  Iteration Semirings. 1-20
  
• Mika Hirvensalo:
  Various Aspects of Finite Quantum Automata. 21-33
  
• Juraj Hromkovic, Georg Schnitger:
  On the Hardness of Determining Small NFA's and of Proving Lower Bounds on Their Sizes. 34-55
  
• Petr Jancar:
  Selected Ideas Used for Decidability and Undecidability of Bisimilarity. 56-71
  
• Jeffrey Shallit:
  The Frobenius Problem and Its Generalizations. 72-83
  
• Flavio D'Alessandro, Stefano Varricchio:
  Well Quasi-orders in Formal Language Theory. 84-95
  

Contributed Papers

• Anil Ada:
  On the Non-deterministic Communication Complexity of Regular Languages. 96-107
  
• Cyril Allauzen, Mehryar Mohri, Ashish Rastogi:
  General Algorithms for Testing the Ambiguity of Finite Automata. 108-120
  
• Mohamed Faouzi Atig, Benedikt Bollig, Peter Habermehl:
  Emptiness of Multi-pushdown Automata Is 2ETIME-Complete. 121-133
  
• Frédérique Bassino, Laura Giambruno, Cyril Nicaud:
  The Average State Complexity of the Star of a Finite Set of Words Is Linear. 134-145
  
• Henning Bordihn, Martin Kutrib, Andreas Malcher:
  On the Computational Capacity of Parallel Communicating Finite Automata. 146-157
  
• Michelangelo Bucci, Aldo de Luca, Alessandro De Luca:
  On a Generalization of Standard Episturmian Morphisms. 158-169
  
• Cristian S. Calude, André Nies, Ludwig Staiger, Frank Stephan:
  Universal Recursively Enumerable Sets of Strings. 170-182
  
• Cristian S. Calude, Marius Zimand:
  Algorithmically Independent Sequences. 183-195
  
• Julien Cassaigne, Tomi Kärki, Luca Q. Zamboni:
  Relationally Periodic Sequences and Subword Complexity. 196-205
  
• Maxime Crochemore, Szilárd Zsolt Fazekas, Costas S. Iliopoulos, Inuka Jayasekera:
  Bounds on Powers in Strings. 206-215
  
• Barbara F. Csima, Bakhadyr Khoussainov:
  When Is Reachability Intrinsically Decidable?. 216-227
  
• Erzsébet Csuhaj-Varjú, Jürgen Dassow, György Vaszil:
  Some New Modes of Competence-Based Derivations in CD Grammar Systems. 228-239
  
• Arturo Carpi, Flavio D'Alessandro:
  The Synchronization Problem for Strongly Transitive Automata. 240-251
  
• Rodrigo de Souza:
  On the Decidability of the Equivalence for k-Valued Transducers. 252-263
  
• Alberto Dennunzio, Enrico Formenti:
  Decidable Properties of 2D Cellular Automata. 264-275
  
• Bruno Durand, Andrei E. Romashchenko, Alexander Shen:
  Fixed Point and Aperiodic Tilings. 276-288
  
• Joost Engelfriet, Eric Lilin, Andreas Maletti:
  Extended Multi Bottom-Up Tree Transducers. 289-300
  
• Javier Esparza, Stefan Kiefer, Michael Luttenberger:
  Derivation Tree Analysis for Accelerated Fixed-Point Computation. 301-313
  
• Emmanuel Filiot, Jean-Marc Talbot, Sophie Tison:
  Tree Automata with Global Constraints. 314-326
  
• Dominik D. Freydenberger, Daniel Reidenbach:
  Bad News on Decision Problems for Patterns. 327-338
  
• Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
  Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time. 339-358
  
• Viliam Geffert, Carlo Mereghetti, Beatrice Palano:
  More Concise Representation of Regular Languages by Automata and Regular Expressions. 359-370
  
• Jens Glöckler:
  A Taxonomy of Deterministic Forgetting Automata. 371-382
  
• Hermann Gruber, Markus Holzer:
  Provably Shorter Regular Expressions from Deterministic Finite Automata. 383-395
  
• Jana Hadravová, Stepan Holub:
  Large Simple Binary Equality Words. 396-407
  
• Stepan Holub, Dirk Nowotka:
  On the Relation between Periodicity and Unbordered Factors of Finite Words. 408-418
  
• Masami Ito, Lila Kari, Zachary Kincaid, Shinnosuke Seki:
  Duplication in DNA Sequences. 419-430
  
• Galina Jirásková:
  On the State Complexity of Complements, Stars, and Reversals of Regular Languages. 431-442
  
• Galina Jirásková, Alexander Okhotin:
  On the State Complexity of Operations on Two-Way Finite Automata. 443-454
  
• Christos A. Kapoutsis, Richard Královic, Tobias Mömke:
  On the Size Complexity of Rotating and Sweeping Automata. 455-466
  
• Juhani Karhumäki, Aleksi Saarela:
  An Analysis and a Reproof of Hmelevskii's Theorem. 467-478
  
• Ondrej Klíma, Libor Polák:
  Hierarchies of Piecewise Testable Languages. 479-490
  
• Dietrich Kuske, Ingmar Meinecke:
  Construction of Tree Automata from Regular Expressions. 491-503
  
• Roberto Mantaci, Sabrina Mantaci, Antonio Restivo:
  Balance Properties and Distribution of Squares in Circular Words. 504-515
  
• Rémi Morin:
  MSO Logic for Unambiguous Shared-Memory Systems. 516-528
  
• Victor L. Selivanov, Klaus W. Wagner:
  Complexity of Topological Properties of Regular omega-Languages. 529-542
  

Last update Wed Feb 15 04:59:38 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page