Implementation and Application of Automata: 9th International Conference, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers (Lecture ... Computer Science and General Issues)

This book constitutes the thoroughly refereed post-proceedings of the 9th International Conference on Implementation and Application of Automata, CIAA 2004, held in Kingston, Canada in July 2004. The 25 revised full papers and 14 revised poster papers presented together with 2 invited contributions have gone through two rounds of reviewing and improvement. The topics covered range from applications of automata in natural language and speech processing to protein sequencing and gene compression, and from state complexity and new algorithms for automata operations to applications of quantum finite automata. Table of Contents......Page 10 Automata-Theoretic Techniques for Analyzing Infinite-State Systems......Page 14 Enumerating Regular Expressions and Their Languages......Page 15 A General Weighted Grammar Library......Page 36 On the Complexity of Hopcroft’s State Minimization Algorithm......Page 48 Implementation of Catalytic P Systems......Page 58 Code Selection by Tree Series Transducers......Page 70 Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages......Page 81 Brute Force Determinization of NFAs by Means of State Covers......Page 93 Computing the Follow Automaton of an Expression......Page 103 Viral Gene Compression: Complexity and Verification......Page 115 Concatenation State Machines and Simple Functions......Page 126 FIRE Station: An Environment for Manipulating Finite Automata and Regular Expression Views......Page 138 Finding Finite Automata That Certify Termination of String Rewriting......Page 147 Linear Encoding Scheme for Weighted Finite Automata......Page 159 The Generalization of Generalized Automata: Expression Automata......Page 169 An Automata Approach to Match Gapped Sequence Tags Against Protein Database......Page 180 State Complexity of Concatenation and Complementation of Regular Languages......Page 191 Minimal Unambiguous εNFA......Page 203 Substitutions, Trajectories and Noisy Channels......Page 215 State Complexity and the Monoid of Transformations of a Finite Set......Page 226 An Application of Quantum Finite Automata to Interactive Proof Systems......Page 238 Time and Space Efficient Algorithms for Constrained Sequence Alignment......Page 250 Stochastic Context-Free Graph Grammars for Glycoprotein Modelling......Page 260 Parametric Weighted Finite Automata for Figure Drawing......Page 272 Regional Finite-State Error Repair......Page 282 Approximating Dependency Grammars Through Intersection of Regular Languages......Page 294 On the Equivalence-Checking Problem for a Model of Programs Related with Multi-tape Automata......Page 306 Tight Bounds for NFA to DFCA Transformations for Binary Alphabets......Page 319 Simulating the Process of Gene Assembly in Ciliates......Page 321 A BDD-Like Implementation of an Automata Package......Page 323 Approximation to the Smallest Regular Expression for a Given Regular Language......Page 325 Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn-Rhodes Theory......Page 328 Does Hausdorff Dimension Measure Texture Complexity?......Page 330 Combining Regular Expressions with (Near-)Optimal Brzozowski Automata......Page 332 From Automata to Semilinear Sets: A Logical Solution for Sets L(C,P)......Page 334 Myhill-Nerode Theorem for Sequential Transducers over Unique GCD-Monoids......Page 336 Minimalizations of NFA Using the Universal Automaton......Page 338 Two-Dimensional Pattern Matching by Two-Dimensional Online Tessellation Automata......Page 340 Size Reduction of Multitape Automata......Page 342 Testability of Oracle Automata......Page 344 Magic Numbers for Symmetric Difference NFAs......Page 346 U......Page 348 Z......Page 349 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. 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 Michael Domaratzki ... [et Al.] (eds.). Includes Bibliographical References And Index. Also Issued Online.