Implementation and Application of Automata

1. Front Matter

   PDF

2. Invited Talks

   1. Cover Languages and Implementations

      • Cezar Câmpeanu

      Pages 1-1

   2. Automata for Codes

      • Helmut Jürgensen

      Pages 2-15

   3. Applications of Symbolic Finite Automata

      • Margus Veanes

      Pages 16-23

3. Regular Papers

   1. Computing Weights

      • Houda Abbad, Éric Laugerotte

      Pages 24-35

   2. Partial Word DFAs

      • Eric Balkanski, F. Blanchet-Sadri, Matthew Kilgore, B. J. Wyatt

      Pages 36-47

   3. Using Regular Grammars for Event-Based Testing

      • Fevzi Belli, Mutlu Beyazıt

      Pages 48-59

   4. Two-Pass Greedy Regular Expression Parsing

      • Niels Bjørn Bugge Grathwohl, Fritz Henglein, Lasse Nielsen, Ulrik Terp Rasmussen

      Pages 60-71

   5. Universal Witnesses for State Complexity of Basic Operations Combined with Reversal

      • Janusz Brzozowski, David Liu

      Pages 72-83

   6. Trimming Visibly Pushdown Automata

      • Mathieu Caralp, Pierre-Alain Reynier, Jean-Marc Talbot

      Pages 84-96

   7. A Uniformization Theorem for Nested Word to Word Transductions

      • Dmitry Chistikov, Rupak Majumdar

      Pages 97-108

   8. Towards Nominal Context-Free Model-Checking

      • Pierpaolo Degano, Gian-Luigi Ferrari, Gianluca Mezzetti

      Pages 109-121

   9. Implementation Concepts in Vaucanson 2

      • Akim Demaille, Alexandre Duret-Lutz, Sylvain Lombardy, Jacques Sakarovitch

      Pages 122-133

   10. A Completion Algorithm for Lattice Tree Automata

       • Thomas Genet, Tristan Le Gall, Axel Legay, Valérie Murat

       Pages 134-145

   11. Approximate Matching between a Context-Free Grammar and a Finite-State Automaton

       • Yo-Sub Han, Sang-Ki Ko, Kai Salomaa

       Pages 146-157

   12. On Palindromic Sequence Automata and Applications

       • Md. Mahbubul Hasan, A. S. M. Sohidull Islam, M. Sohel Rahman, Ayon Sen

       Pages 158-168

   13. LALBLC A Program Testing the Equivalence of dpda’s

       • Patrick Henry, Géraud Sénizergues

       Pages 169-180

   14. Brzozowski’s Minimization Algorithm—More Robust than Expected

       • Markus Holzer, Sebastian Jakobi

       Pages 181-192

   15. Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languages

       • Oscar H. Ibarra, Bala Ravikumar

       Pages 193-207

   16. On the Boundary of Regular Languages

       • Jozef Jirásek, Galina Jirásková

       Pages 208-219

This book constitutes the thoroughly refereed papers of the 18th International Conference on Implementation and Application of Automata, CIAA 2013, held in Halifax, NS, Canada, in July 2013. The 25 revised full papers presented together with 3 invited papers and 7 short papers were carefully selected from 43 submissions. The papers cover various topics such as complexity of automata; compressed automata; counter automata; dictionary matching; edit distance; homing sequences; implementation; minimization of automata; model checking; parsing of regular expressions; partial word automata; picture languages; pushdown automata; queue automata; reachability analysis for software verification; restarting automata; transducers; tree automata; weighted automata; XML streams.

• context-free language
• deterministic finite automata
• model checking
• regular languages
• uniformization
• algorithm analysis and problem complexity
• data structures

• Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, Canada

  Stavros Konstantinidis

Policies and ethics