9. CIAA 2004: Kingston, Ontario, Canada

Invited Papers

• Oscar H. Ibarra:
  Automata-Theoretic Techniques for Analyzing Infinite-State Systems. 1
  
• Jonathan Lee, Jeffrey Shallit:
  Enumerating Regular Expressions and Their Languages. 2-22
  

Contributed Papers

• Cyril Allauzen, Mehryar Mohri, Brian Roark:
  A General Weighted Grammar Library. 23-34
  
• Jean Berstel, Olivier Carton:
  On the Complexity of Hopcroft's State Minimization Algorithm. 35-44
  
• Aneta Binder, Rudolf Freund, Georg Lojka, Marion Oswald:
  Implementation of Catalytic P Systems. 45-56
  
• Björn Borchardt:
  Code Selection by Tree Series Transducers. 57-67
  
• Henning Bordihn, Markus Holzer, Martin Kutrib:
  Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages. 68-79
  
• Jean-Marc Champarnaud, Fabien Coulon, Thomas Paranthoën:
  Brute Force Determinization of NFAs by Means of State Covers. 80-89
  
• Jean-Marc Champarnaud, Florent Nicart, Djelloul Ziadi:
  Computing the Follow Automaton of an Expression. 90-101
  
• Mark Daley, Ian McQuillan:
  Viral Gene Compression: Complexity and Verification. 102-112
  
• Wojciech Debski, Wojciech Fraczak:
  Concatenation State Machines and Simple Functions. 113-124
  
• Michiel Frishert, Loek G. Cleophas, Bruce W. Watson:
  FIRE Station: An Environment for Manipulating Finite Automata and Regular Expression Views. 125-133
  
• Alfons Geser, Dieter Hofbauer, Johannes Waldmann, Hans Zantema:
  Finding Finite Automata That Certify Termination of String Rewriting. 134-145
  
• Mathieu Giraud, Dominique Lavenier:
  Linear Encoding Scheme for Weighted Finite Automata. 146-155
  
• Yo-Sub Han, Derick Wood:
  The Generalization of Generalized Automata: Expression Automata. 156-166
  
• Yonghua Han, Bin Ma, Kaizhong Zhang:
  An Automata Approach to Match Gapped Sequence Tags Against Protein Database. 167-177
  
• Jozef Jirásek, Galina Jirásková, Alexander Szabari:
  State Complexity of Concatenation and Complementation of Regular Languages. 178-189
  
• Sebastian John:
  Minimal Unambiguous eNFA. 190-201
  
• Lila Kari, Stavros Konstantinidis, Petr Sosík:
  Substitutions, Trajectories and Noisy Channels. 202-212
  
• Bryan Krawetz, John Lawrence, Jeffrey Shallit:
  State Complexity and the Monoid of Transformations of a Finite Set. 213-224
  
• Harumichi Nishimura, Tomoyuki Yamakami:
  An Application of Quantum Finite Automata to Interactive Proof Systems. 225-236
  
• Z. S. Peng, H. F. Ting:
  Time and Space Efficient Algorithms for Constrained Sequence Alignment. 237-246
  
• Baozhen Shan:
  Stochastic Context-Free Graph Grammars for Glycoprotein Modelling. 247-258
  
• German Tischler:
  Parametric Weighted Finite Automata for Figure Drawing. 259-268
  
• Manuel Vilares Ferro, Juan Otero, Jorge Graña Gil:
  Regional Finite-State Error Repair. 269-280
  
• Anssi Yli-Jyrä:
  Approximating Dependency Grammars Through Intersection of Regular Languages. 281-292
  
• Vladimir A. Zakharov, Ivan Zakharyaschev:
  On the Equivalence-Checking Problem for a Model of Programs Related with Multi-tape Automata. 293-305
  

Poster Papers

• Cezar Câmpeanu, Andrei Paun:
  Tight Bounds for NFA to DFCA Transformations for Binary Alphabets. 306-307
  
• Liliana Cojocaru:
  Simulating the Process of Gene Assembly in Ciliates. 308-309
  
• Jean-Michel Couvreur:
  A BDD-Like Implementation of an Automata Package. 310-311
  
• Manuel Delgado, José Morais:
  Approximation to the Smallest Regular Expression for a Given Regular Language. 312-314
  
• Attila Egri-Nagy, Chrystopher L. Nehaniv:
  Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn-Rhodes Theory. 315-316
  
• Mark G. Eramian, Matthew Drotar:
  Does Hausdorff Dimension Measure Texture Complexity?. 317-318
  
• Michiel Frishert, Bruce W. Watson:
  Combining Regular Expressions with (Near-)Optimal Brzozowski Automata. 319-320
  
• Denis Lugiez:
  From Automata to Semilinear Sets: A Logical Solution for Sets L(C, P). 321-322
  
• Andreas Maletti:
  Myhill-Nerode Theorem for Sequential Transducers over Unique GCD-Monoids. 323-324
  
• Libor Polák:
  Minimalizations of NFA Using the Universal Automaton. 325-326
  
• Tomás Polcar, Borivoj Melichar:
  Two-Dimensional Pattern Matching by Two-Dimensional Online Tessellation Automata. 327-328
  
• Hellis Tamm, Matti Nykänen, Esko Ukkonen:
  Size Reduction of Multitape Automata. 329-330
  
• Gaoyan Xie, Cheng Li, Zhe Dang:
  Testability of Oracle Automata. 331-332
  
• Lynette van Zijl:
  Magic Numbers for Symmetric Difference NFAs. 333-334