Implementation and Application of Automata

1. Front Matter

   Pages I-XXIII

   PDF

2. Invited Papers

   1. Front Matter

      Pages 1-1

      PDF

   2. Automata and Logics for Concurrent Systems: Five Models in Five Pages

      • Benedikt Bollig

      Pages 3-12

   3. Hardware Implementations of Finite Automata and Regular Expressions

      • Bruce W. Watson

      Pages 13-17

3. Regular Papers

   1. Front Matter

      Pages 19-19

      PDF

   2. Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems

      • Abhijin Adiga, Chris J. Kuhlman, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns

      Pages 21-34

   3. From Ambiguous Regular Expressions to Deterministic Parsing Automata

      • Angelo Borsotti, Luca Breveglieri, Stefano Crespi Reghizzi, Angelo Morzenti

      Pages 35-48

   4. Deciding Synchronous Kleene Algebra with Derivatives

      • Sabine Broda, Sílvia Cavadas, Miguel Ferreira, Nelma Moreira

      Pages 49-62

   5. On the Hierarchy of Block Deterministic Languages

      • Pascal Caron, Ludovic Mignot, Clément Miklarz

      Pages 63-75

   6. Security of Numerical Sensors in Automata

      • Zhe Dang, Dmitry Dementyev, Thomas R. Fischer, William J. Hutton III

      Pages 76-88

   7. Jumping Finite Automata: Characterizations and Complexity

      • Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid

      Pages 89-101

   8. Run-Length Encoded Nondeterministic KMP and Suffix Automata

      • Emanuele Giaquinta

      Pages 102-113

   9. More on Deterministic and Nondeterministic Finite Cover Automata

      • Hermann Gruber, Markus Holzer, Sebastian Jakobi

      Pages 114-126

   10. On the Number of Synchronizing Colorings of Digraphs

       • Vladimir V. Gusev, Marek Szykuła

       Pages 127-139

   11. On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism

       • Pierre-Cyrille Héam, Jean-Luc Joly

       Pages 140-152

   12. Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata

       • Pierre-Cyrille Héam, Jean-Luc Joly

       Pages 153-164

   13. Subword Metrics for Infinite Words

       • Stefan Hoffmann, Ludwig Staiger

       Pages 165-175

   14. From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods

       • Mans Hulden

       Pages 176-187

   15. Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata

       • Natalia Kushik, Nina Yevtushenko

       Pages 188-198

   16. Expressive Capacity of Concatenation Freeness

       • Martin Kutrib, Matthias Wendlandt

       Pages 199-210

This book constitutes the refereed proceedings of the 20th International Conference on Implementation and Application of Automata, CIAA 2015, held in held in Umeå, Sweden, in August 2015.
The 22 revised full papers presented together with 4 invited papers and 2 toool demonstration papers were carefully reviewed and selected from 49 submissions. The papers cover all aspects of cover automata, counter automata, decision algorithms on automata, descriptional complexity, expressive power of automata, homing sequences, jumping finite automata, multi-dimensional languages, parsing and pattern matching, quantum automata, realtime pushdown automata, random generation of automata, regular expressions, security issues, sensors in automata, transducers, transformation of automata, and weighted automata.

• Automaton
• Computational complexity
• Concurrent system
• Context-free grammar
• Descriptional complexity
• Finite-state machine
• Formal language
• Grammar
• Implementation
• Parsing
• Probabilistic computation
• Quantum automaton
• Quantum computation
• Recognition power
• Regular expression
• Security
• Semantic bugs
• Syntax tree
• Undecidability
• Weighted automaton
• algorithm analysis and problem complexity

• Umeå University, Umeå, Sweden

  Frank Drewes

Policies and ethics