Implementation and Application of Automata

1. Front Matter

   PDF

2. Invited Talks

   1. Spiking Neural P Systems Used as Acceptors and Transducers

      • Gheorghe Păun

      Pages 1-4

   2. Linear-Time Model Checking: Automata Theory in Practice

      • Moshe Y. Vardi

      Pages 5-10

   3. OpenFst: A General and Efficient Weighted Finite-State Transducer Library

      • Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wojciech Skut, Mehryar Mohri

      Pages 11-23

   4. Automata Applications in Chip-Design Software

      • Bruce W. Watson

      Pages 24-26

3. Contributed Talks

   1. Synchronizing Automata Preserving a Chain of Partial Orders

      • Mikhail V. Volkov

      Pages 27-37

   2. Reducing Acyclic Cover Transducers

      • Jean-Marc Champarnaud, Franck Guingne, Jacques Farré

      Pages 38-50

   3. On-the-Fly Stuttering in the Construction of Deterministic ω-Automata

      • Joachim Klein, Christel Baier

      Pages 51-61

   4. Average Value and Variance of Pattern Statistics in Rational Models

      • Massimiliano Goldwurm, Roberto Radicioni

      Pages 62-72

   5. Weighted Automata and Weighted Logics with Discounting

      • Manfred Droste, George Rahonis

      Pages 73-84

   6. Regulated Nondeterminism in Pushdown Automata

      • Martin Kutrib, Andreas Malcher, Larissa Werlein

      Pages 85-96

   7. Deterministic Caterpillar Expressions

      • Kai Salomaa, Sheng Yu, Jinfeng Zan

      Pages 97-108

   8. Backward and Forward Bisimulation Minimisation of Tree Automata

      • Johanna Högberg, Andreas Maletti, Jonathan May

      Pages 109-121

   9. An Implementation of Deterministic Tree Automata Minimization

      • Rafael C. Carrasco, Jan Daciuk, Mikel L. Forcada

      Pages 122-129

   10. Accelerating Boyer Moore Searches on Binary Texts

       • Shmuel T. Klein, Miri Kopel Ben-Nissan

       Pages 130-143

   11. On the Suffix Automaton with Mismatches

       • Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi

       Pages 144-156

   12. On String Matching in Chunked Texts

       • Hannu Peltola, Jorma Tarhio

       Pages 157-167

   13. Factor Automata of Automata and Applications

       • Mehryar Mohri, Pedro Moreno, Eugene Weinstein

       Pages 168-179

   14. Subset Seed Automaton

       • Gregory Kucherov, Laurent Noé, Mikhail Roytberg

       Pages 180-191

   15. A Measure for the Degree of Nondeterminism of Context-Free Languages

       • František Mráz, Martin Plátek, Friedrich Otto

       Pages 192-202

The 12th International Conference on Implementation and Application of - tomata CIAA 2007 washeld at the Czech Technical Universityin Prague,Czech Republic on July 16–18, 2007. These proceedings contain the papers that were presented at CIAA 2007, as well as the abstracts of the poster papers that were displayed during the conference. The proceedings also include the abstracts and extended abstracts offourinvitedlecturespresentedbyGheorghePau ? n,MichaelRiley,MosheVardi, and Bruce W. Watson. The 23 regular papers and 7 poster papers were selected from 79 submitted papers covering various topics in the theory, implementation, and application of automataandrelatedstructures.Eachsubmitted paper wasreviewedbyatleast threeProgramCommitteemembers,with the assistanceofreferees.Theauthors of the papers presented here come from the following countries: Canada, Czech Republic, Denmark, Finland, France, Germany, Greece, Israel, Italy, Poland, Romania, Russia, South Africa, Spain, Sweden, UK, and USA. We wish to thank all those who made this meeting possible: the authors for submitting papers, the Program Committee members and external referees (listed on pages VII and VIII) for their excellent work, and last but not least our four invited speakers. Finally, we wish to express our sincere appreciation to the sponsors and local organizers.

• Alphabet
• Bisimulation
• Simulation
• automata
• automata implementations
• automata theory
• bioinformatics
• chip design
• complexity theory
• context-free grammar
• decidability
• determinism
• finite automata
• grammar
• model checking
• algorithm analysis and problem complexity

Policies and ethics