Ebook: Implementation and Application of Automata: 12th International Conference, CIAA 2007, Praque, Czech Republic, July 16-18, 2007, Revised Selected Papers

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.

---

This book constitutes the thoroughly refereed post-proceedings of the 12th International Conference on Implementation and Application of Automata, CIAA 2007, held in Prague, Czech Republic, in July 2007.

The 23 revised full papers and seven revised poster papers presented together with the extended abstracts of four invited lectures were carefully reviewed and selected from 79 submissions and have gone through two rounds of reviewing and improvement. The papers cover various topics in the theory, implementation, and applications of automata and related structures.

---

This book constitutes the thoroughly refereed post-proceedings of the 12th International Conference on Implementation and Application of Automata, CIAA 2007, held in Prague, Czech Republic, in July 2007.

The 23 revised full papers and seven revised poster papers presented together with the extended abstracts of four invited lectures were carefully reviewed and selected from 79 submissions and have gone through two rounds of reviewing and improvement. The papers cover various topics in the theory, implementation, and applications of automata and related structures.

Content:
Front Matter....Pages -
Spiking Neural P Systems Used as Acceptors and Transducers....Pages 1-4
Linear-Time Model Checking: Automata Theory in Practice....Pages 5-10
OpenFst: A General and Efficient Weighted Finite-State Transducer Library....Pages 11-23
Automata Applications in Chip-Design Software....Pages 24-26
Synchronizing Automata Preserving a Chain of Partial Orders....Pages 27-37
Reducing Acyclic Cover Transducers....Pages 38-50
On-the-Fly Stuttering in the Construction of Deterministic ?-Automata....Pages 51-61
Average Value and Variance of Pattern Statistics in Rational Models....Pages 62-72
Weighted Automata and Weighted Logics with Discounting....Pages 73-84
Regulated Nondeterminism in Pushdown Automata....Pages 85-96
Deterministic Caterpillar Expressions....Pages 97-108
Backward and Forward Bisimulation Minimisation of Tree Automata....Pages 109-121
An Implementation of Deterministic Tree Automata Minimization....Pages 122-129
Accelerating Boyer Moore Searches on Binary Texts....Pages 130-143
On the Suffix Automaton with Mismatches....Pages 144-156
On String Matching in Chunked Texts....Pages 157-167
Factor Automata of Automata and Applications....Pages 168-179
Subset Seed Automaton....Pages 180-191
A Measure for the Degree of Nondeterminism of Context-Free Languages....Pages 192-202
Efficient Computation of Throughput Values of Context-Free Languages....Pages 203-213
Analyzing Ambiguity of Context-Free Grammars....Pages 214-225
Efficient Enumeration of Regular Languages....Pages 226-242
Multi-grain Relations....Pages 243-252
Memory Reduction for Strategies in Infinite Games....Pages 253-264
Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms....Pages 265-276
Finite State Automata Representing Two-Dimensional Subshifts....Pages 277-289
Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages....Pages 290-302
A Finite-State Super-Chunker....Pages 303-305
The Constrained Longest Common Subsequence Problem for Degenerate Strings....Pages 306-308
Finite Automata Accepting Star-Connected Languages....Pages 309-311
Efficiently Matching with Local Grammars Using Prefix Overlay Transducers....Pages 312-313
Significant Subpatterns Matching ....Pages 314-316
A New Method for Compiling Parallel Replacement Rules....Pages 317-319
Back Matter....Pages 320-321
....Pages -