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.
Author(s): Michael Domaratzki, Alexander Okhotin, Kai Salomaa, Sheng Yu
Edition: 1
Year: 2005
Language: English
Pages: 348
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
