7. DCFS 2005: Como, Italy

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini, Detlef Wotschke (Eds.): 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30 - July 2, 2005. Proceedings. Università degli Studi di Milano, Milan, Italy 2005

Invited Papers

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano: Some formal methods for analyzing quantum automata. 1-14
Egon Börger: Using Abstract State Machines for the Description and the Analysis of Formal Systems. 15-22
Viliam Geffert: (Non)determinism and the Size of One-Way Finite Automata. 23-37
Juraj Hromkovic, Georg Schnitger: Communication Complexity Method for Proving Lower Bounds on Descriptional Complexity in Automata and Formal Language Theory. 38-38
Ludwig Staiger: The Kolmogorov complexity of infinite objects. 39-50

Regular Papers

Henning Bordihn, Henning Fernau: The degree of parallelism. 51-62
Henning Bordihn, Bettina Sunckel: On active symbols in CD grammar systems. 63-74
Cezar Câmpeanu, Nicolae Santean, Sheng Yu: Large NFA Without Mergeable States. 75-84
Michael Domaratzki, Alexander Okhotin, Jeffrey Shallit: Enumeration of Context-Free Languages and Related Structures. 85-96
Berke Durak: Two-way non-deterministic finite automata with a write-once track recognize regular languages only. 97-109
Henning Fernau, Rudolf Freund, Marion Oswald, Klaus Reinhardt: Refining the Nonterminal Complexity of Graph-controlled Grammars. 110-121
Gregor Gramlich, Ralf Herrmann: Learning Unary Automata. 122-133
Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustin Riscos-Núñez: Multidimensional Descriptional Complexity of P Systems. 134-145
Yo-Sub Han, Gerhard Trippen, Derick Wood: Simple-Regular Expressions and Languages. 146-157
Markus Holzer, Martin Kutrib, Jens Reimann: Descriptional Complexity of Deterministic Restarting Automata. 158-169
Marek Hricko, Galina Jirásková, Alexander Szabari: Union and Intersection of Regular Languages and Descriptional Complexity. 170-181
Galina Jirásková, Alexander Okhotin: State complexity of cyclic shift. 182-193
Christos A. Kapoutsis: Deterministic moles cannot solve liveness. 194-205
Lila Kari, Petr Sosík: On Weight of Universal Insertion Grammars. 206-214
Andreas Malcher: On Recursive and Non-Recursive Trade-Offs Between Finite-Turn Pushdown Automata. 215-226
György Vaszil: Non-returning PC Grammar Systems Generate Any Recursively Enumerable Language with Eight Context-free Components. 227-235

Short Papers

Franziska Biegler: Synchronization Functions of Synchronized Context-Free Grammars and Languages. 236-244
Miklós Krész: On the descriptional complexity of soliton automata. 245-252
Kuppuswamy Lakshmanan: Incompatible Measures of Internal Contextual Grammars. 253-260
Libor Polák: Remarks on Multiple Entry Deterministic Finite Automata. 261-268
Rogério Reis, Nelma Moreira, Marco Almeida: On the Representation of Finite Automata. 269-276
Bettina Sunckel: A note on the descriptional complexity of CD grammar systems of finite index. 277-284
Sergey Verlan: On minimal context-free insertion-deletion systems. 285-292

Last update Thu May 24 04:16:11 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page