Implementation and Application of Automata

1. Front Matter

   PDF

2. Using Automata to Describe Self-Assembled Nanostructures

   • Nataša Jonoska

   Pages 1-3

3. A Summary of Some Discrete-Event System Control Problems

   • Karen Rudie

   Pages 4-16

4. Large-Scale Training of SVMs with Automata Kernels

   • Cyril Allauzen, Corinna Cortes, Mehryar Mohri

   Pages 17-27

5. Filters for Efficient Composition of Weighted Finite-State Transducers

   • Cyril Allauzen, Michael Riley, Johan Schalkwyk

   Pages 28-38

6. Incremental DFA Minimisation

   • Marco Almeida, Nelma Moreira, Rogério Reis

   Pages 39-48

7. Finite Automata for Generalized Approach to Backward Pattern Matching

   • Jan Antoš, Bořivoj Melichar

   Pages 49-58

8. Partial Derivative Automata Formalized in Coq

   • José Bacelar Almeida, Nelma Moreira, David Pereira, Simão Melo de Sousa

   Pages 59-68

9. Regular Geometrical Languages and Tiling the Plane

   • Jean-Marc Champarnaud, Jean-Philippe Dubernard, Hadrien Jeanne

   Pages 69-78

10. COMPAS - A Computing Package for Synchronization

    • Krzysztof Chmiel, Adam Roman

    Pages 79-86

11. From Sequential Extended Regular Expressions to NFA with Symbolic Labels

    • Alessandro Cimatti, Sergio Mover, Marco Roveri, Stefano Tonetta

    Pages 87-94

12. State Complexity of Catenation Combined with Union and Intersection

    • Bo Cui, Yuan Gao, Lila Kari, Sheng Yu

    Pages 95-104

13. Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)

    • Volker Diekert, Steffen Kopecki

    Pages 105-114

14. On Straight Words and Minimal Permutators in Finite Transformation Semigroups

    • Attila Egri-Nagy, Chrystopher L. Nehaniv

    Pages 115-124

15. On Lazy Representations and Sturmian Graphs

    • Chiara Epifanio, Christiane Frougny, Alessandra Gabriele, Filippo Mignosi, Jeffrey Shallit

    Pages 125-134

16. Symbolic Dynamics, Flower Automata and Infinite Traces

    • Wit Foryś, Piotr Oprocha, Slawomir Bakalarski

    Pages 135-142

17. The Cayley-Hamilton Theorem for Noncommutative Semirings

    • Radu Grosu

    Pages 143-153

18. Approximating Minimum Reset Sequences

    • Michael Gerbush, Brent Heeringa

    Pages 154-162

19. Transductions Computed by PC-Systems of Monotone Deterministic Restarting Automata

    • Norbert Hundeshagen, Friedrich Otto, Marcel Vollweiler

    Pages 163-172

20. Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization

    • J. Howard Johnson

    Pages 173-180

This book constitutes the thoroughly refereed papers of the 15th International Conference on Implementation and Application of Automata, CIAA 2010, held in Manitoba, Winnipeg, Canada, in August 2010. The 26 revised full papers together with 6 short papers were carefully selected from 52 submissions. The papers cover various topics such as applications of automata in computer-aided verification; natural language processing; pattern matching, data storage and retrieval; bioinformatics; algebra; graph theory; and foundational work on automata theory.

• algebra
• automata kernels
• complexity
• finite automata
• finite-state machines
• formal languages
• games
• graph theory
• nanostructures
• regular expressions
• self-assembly
• tiling
• tree automata
• algorithm analysis and problem complexity
• data structures

• Department of Computer Science, University of Manitoba, Winnipeg, Canada

  Michael Domaratzki

• School of Computing, Queen’s University, Kingston, Canada

  Kai Salomaa

Policies and ethics