Implementation and Application of Automata: 12th International Conference, CIAA 2007, Prague, Czech Republic, July 16-18, 2007, Revised Selected Paper Book

Invited Talks
Spiking Neural P Systems Used as Acceptors and Transducers   Gheorghe Paun     1
Linear-Time Model Checking: Automata Theory in Practice   Moshe Y. Vardi     5
OpenFst: A General and Efficient Weighted Finite-State Transducer Library   Cyril Allauzen   Michael Riley   Johan Schalkwyk   Wojciech Skut   Mehryar Mohri     11
Automata Applications in Chip-Design Software   Bruce W. Watson     24
Contributed Talks
Synchronizing Automata Preserving a Chain of Partial Orders   Mikhail V. Volkov     27
Reducing Acyclic Cover Transducers   Jean-Marc Champarnaud   Franck Guingne   Jacques Farre     38
On-the-Fly Stuttering in the Construction of Deterministic [omega]-Automata   Joachim Klein   Christel Baier     51
Average Value and Variance of Pattern Statistics in Rational Models   Massimiliano Goldwurm   Roberto Radicioni     62
Weighted Automata and Weighted Logics with Discounting   Manfred Droste   George Rahonis     73
Regulated Nondeterminism in Pushdown Automata   Martin Kutrib   Andreas Malcher   Larissa Werlein     85
Deterministic Caterpillar Expressions   KaiSalomaa   Sheng Yu   Jinfeng Zan     97
Backward and Forward Bisimulation Minimisation of Tree Automata   Johanna Hogberg   Andreas Maletti   Jonathan May     109
An Implementation of Deterministic Tree Automata Minimization   Rafael C. Carrasco   Jan Daciuk   Mikel L. Forcada     122
Accelerating Boyer Moore Searches on Binary Texts   Shmuel T. Klein   Miri Kopel Ben-Nissan     130
On the Suffix Automaton with Mismatches   Maxime Crochemore   Chiara Epifanio   Alessandra Gabriele   Filippo Mignosi     144
On String Matching in Chunked Texts   Hannu Peltola   Jorma Tarhio     157
Factor Automata of Automata and Applications   Mehryar Mohri   Pedro Moreno   Eugene Weinstein     168
Subset Seed Automaton   Gregory Kucherov   Laurent Noe   Mikhail Roytberg     180
A Measure for the Degree of Nondeterminism of Context-Free Languages   Frantisek Mraz   Martin Platek   Friedrich Otto     192
Efficient Computation of Throughput Values of Context-Free Languages   Didier Caucal   Jurek Czyzowicz   Wojciech Fraczak   Wojciech Rytter     203
Analyzing Ambiguity of Context-Free Grammars   Claus Brabrand   Robert Giegerich   Anders Moller     214
Efficient Enumeration of Regular Languages   Margareta Ackerman   Jeffrey Shallit     226
Multi-grain Relations   Francois Barthelemy     243
Memory Reduction for Strategies in Infinite Games   Michael Holtmann   Christof Loding     253
Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms   Magnus Steinby   Catalin Ionut Tirnauca     265
Finite State Automata Representing Two-Dimensional Subshifts   Natasa Jonoska   Joni B. Pirnot     277
Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages   Marcella Anselmo   Dora Giammarresi   Maria Madonia     290
Poster Abstracts
REGAL: A Library to Randomly and Exhaustively Generate Automata   Frederique Bassino   Julien David   Cyril Nicaud     303
A Finite-State Super-Chunker   Olivier Blanc   Matthieu Constant   Patrick Watrin     306
The Constrained Longest Common Subsequence Problem for Degenerate Strings   Costas Iliopoulos   M. Sohel Rahman   Michal Voracek   Ladislav Vagner     309
Finite Automata Accepting Star-Connected Languages   Barbara Klunder     312
Efficiently Matching with Local Grammars Using Prefix Overlay Transducers   Clemens Marschner     314
Significant Subpatterns Matching   Jan Supol     317
A New Method for Compiling Parallel Replacement Rules   Anssi Yli-Jyra   Kimmo Koskenniemi     320
Author Index     323