Implementation and Application of Automata

1. Front Matter

   PDF

2. Invited Papers

   1. Automata-Theoretic Techniques for Analyzing Infinite-State Systems

      • Oscar H. Ibarra

      Pages 1-1

   2. Enumerating Regular Expressions and Their Languages

      • Jonathan Lee, Jeffrey Shallit

      Pages 2-22

3. Contributed Papers

   1. A General Weighted Grammar Library

      • Cyril Allauzen, Mehryar Mohri, Brian Roark

      Pages 23-34

   2. On the Complexity of Hopcroft’s State Minimization Algorithm

      • Jean Berstel, Olivier Carton

      Pages 35-44

   3. Implementation of Catalytic P Systems

      • Aneta Binder, Rudolf Freund, Georg Lojka, Marion Oswald

      Pages 45-56

   4. Code Selection by Tree Series Transducers

      • Björn Borchardt

      Pages 57-67

   5. Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages

      • Henning Bordihn, Markus Holzer, Martin Kutrib

      Pages 68-79

   6. Brute Force Determinization of NFAs by Means of State Covers

      • Jean-Marc Champarnaud, Fabien Coulon, Thomas Paranthoën

      Pages 80-89

   7. Computing the Follow Automaton of an Expression

      • Jean-Marc Champarnaud, Florent Nicart, Djelloul Ziadi

      Pages 90-101

   8. Viral Gene Compression: Complexity and Verification

      • Mark Daley, Ian McQuillan

      Pages 102-112

   9. Concatenation State Machines and Simple Functions

      • Wojciech Debski, Wojciech Fraczak

      Pages 113-124

   10. FIRE Station: An Environment for Manipulating Finite Automata and Regular Expression Views

       • Michiel Frishert, Loek Cleophas, Bruce W. Watson

       Pages 125-133

   11. Finding Finite Automata That Certify Termination of String Rewriting

       • Alfons Geser, Dieter Hofbauer, Johannes Waldmann, Hans Zantema

       Pages 134-145

   12. Linear Encoding Scheme for Weighted Finite Automata

       • Mathieu Giraud, Dominique Lavenier

       Pages 146-155

   13. The Generalization of Generalized Automata: Expression Automata

       • Yo-Sub Han, Derick Wood

       Pages 156-166

   14. An Automata Approach to Match Gapped Sequence Tags Against Protein Database

       • Yonghua Han, Bin Ma, Kaizhong Zhang

       Pages 167-177

   15. State Complexity of Concatenation and Complementation of Regular Languages

       • Jozef Jirásek, Galina Jirásková, Alexander Szabari

       Pages 178-189

   16. Minimal Unambiguous εNFA

       • Sebastian John

       Pages 190-201

   17. Substitutions, Trajectories and Noisy Channels

       • Lila Kari, Stavros Konstantinidis, Petr Sosík

       Pages 202-212

This volume of Lecture Notes in Computer Science contains the revised versions of the papers presented at the 9th International Conference on Implemen- tion and Application of Automata, CIAA 2004. Also included are the extended abstracts of the posters accepted to the conference. The conference was held at Queen’s University in Kingston, Ontario, Canada on July 22–24, 2004. As for its predecessors, the theme of CIAA 2004 was the implementation of automata and grammars of all types and their application in other ?elds. The topics of the papers presented at the conference range from applications of automata in natural language and speech processing to protein sequencingandgenecompression,andfromstatecomplexityandnewalgorithms for automata operations to applications of quantum ?nite automata. The25regularpapersand14posterpaperswereselectedfrom62submissions totheconference.EachsubmittedpaperwasevaluatedbyatleastthreeProgram Committee members, with the help of external referees. Based on the referee reports, the paper “Substitutions, Trajectories and Noisy Channels” by L. Kari, S. Konstantinidis and P. Sos´ ?k was chosen as the winner of the CIAA 2004 Best Paper Award. The award is sponsored by the University of California at Santa Barbara. The authors of the papers presented here come from the following countries and regions: Austria, Canada, Czech Republic, Finland, France, Germany, Hong Kong, Netherlands, Portugal, Russia, Slovakia, South Africa, Spain, UK, and USA.

• Alphabet
• Pattern Matching
• algorithms
• automata
• complexity
• complexity theory
• concatenation state machines
• finite automata
• finite-state systems
• gene compression
• grammar
• modeling
• regular expressions
• speech processing
• term rewriting
• algorithm analysis and problem complexity

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

  Michael Domaratzki

• Department of Mathematics, University of Turku, Finland

  Alexander Okhotin

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

  Kai Salomaa

• Department of Computer Science, University of Western Ontario, London, Canada

  Sheng Yu

Policies and ethics