4. DCFS 2002: London, Ontario, Canada

Jürgen Dassow, Maia Hoeberechts, Helmut Jürgensen, Detlef Wotschke (Eds.): Fourth International Workshop on Descriptional Complexity of Formal Systems - DCFS 2002, London, Canada, August 21 - 24, 2002. Pre-proceedings. Report No. 586 Department of Computer Science, The University of Western Ontario, Canada 2002, ISBN 0-7714-2388-8

Invited Lectures

Erzsébet Csuhaj-Varjú: Descriptional Complexity Issues in Grammar Systems. 13-16
Keith Ellul, Jeffrey Shallit, Ming-wei Wang: Regular Expressions: New Results and Open Problems. 17-34
Juris Hartmanis: The Separation Problems and Descriptional Complexity. 35
Lucian Ilie, Sheng Yu, Kaizhong Zhang: Repetition Complexity of Words. 36
Martin Kappes: On Possible Extensions and Relationships Between Software Reliability, Software Metrics and Descriptional Complexity. 37-39

Workshop Contributions

M. Sakthi Balan: Complexity Issues in Binding-Blocking Automata. 43-54
Henning Bordihn, Markus Holzer, Martin Kutrib: Economy of Descriptions for Basic Constructions on Rational Transductions. 55-69
Cezar Câmpeanu: How Many States Can Have a Minimal DFA that Accepts Words of Length Less Than or Equal to l? 70-80
Jean-Marc Champarnaud, Georges Hansel, Thomas Paranthoën, Djelloul Ziadi: NFAs bitstream-based random generation. 81-94
Michael Domaratzki, Kai Salomaa: State Complexity of Shuffle on Trajectories. 95-109
Mark G. Eramian: Efficient Simulation of Nondeterministic Weighted Finite Automata. 110-122
Cristian Grozea: NP Predicates Computable in the Weakest Level of the Grzegorczyck Hierarchy. 123-132
Lila Kari, Stavros Konstantinidis: Descriptional Complexity of Error/Edit Systems. 133-147
Mutyam Madhu: Complexity Issues in Rewriting P Systems. 148-159
Andreas Malcher: On One-Way Cellular Automata with a Fixed Number of Cells. 160-173
Andrew Martinez: Efficient Computation of Regular Expressions from Unary NFAs. 174-187
Ian McQuillan: Descriptional Complexity of Block-Synchronization Context-Free Grammars. 188-203
Charlotte L. Miller: Context Derivation Sets and Context-Free Normal Forms. 204-215
Mark-Jan Nederhof, Giorgio Satta: Probabilistic Parsing Strategies. 216-230
Frank Nießner: Büchi automata and their degrees of nondeterminism and ambiguity. 231-245
Taishin Y. Nishida: Descriptional complexities of grammars over alphabets with finite parameters. 246-255
Alexander Okhotin: State complexity of linear conjunctive languages. 256-270

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

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