Implementation and Application of Automata: 10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers

Rūsiņš Freivalds (auth.), Jacques Farré, Igor Litovsky, Sylvain Schmitz (eds.)3540310231, 9783540310235

This book constitutes the thoroughly refereed post-proceedings of the 10th International Conference on Implementation and Application of Automata, CIAA 2005, held in Sophia Antipolis, France, in June 2005.

The 26 revised full papers and 8 revised poster papers presented together with 2 invited contributions were selected from 87 submissions and have gone through two rounds of reviewing and improvement. The topics covered show applications of automata in many fields, including mathematics, linguistics, networks, XML processing, biology and music.

---

Table of contents :
Front Matter….Pages –
Languages Recognizable by Quantum Finite Automata….Pages 1-14
The Language, the Expression, and the (Small) Automaton….Pages 15-30
Minimization of Non-deterministic Automata with Large Alphabets….Pages 31-42
Simulating Two-Dimensional Recognizability by Pushdown and Queue Automata….Pages 43-53
Component Composition Preserving Behavioural Contracts Based on Communication Traces….Pages 54-65
Strong Retiming Equivalence of Synchronous Schemes….Pages 66-77
Prime Normal Form and Equivalence of Simple Grammars….Pages 78-89
An Incremental Algorithm for Constructing Minimal Deterministic Finite Cover Automata….Pages 90-103
Finite Automata and Unions of Regular Patterns with Bounded Constant Segments….Pages 104-115
Inside Vaucanson….Pages 116-128
Deterministic Recognition of Trees Accepted by a Linear Pushdown Tree Automaton….Pages 129-140
Shorter Regular Expressions from Finite-State Automata….Pages 141-152
Wind in the Willows – Generating Music by Means of Tree Transducers….Pages 153-162
On Deterministic Catalytic Systems….Pages 163-175
Restricting the Use of Auxiliary Symbols for Restarting Automata….Pages 176-187
A Class of Rational n -WFSM Auto-intersections….Pages 188-198
Experiments with Deterministic ω -Automata for Formulas of Linear Temporal Logic….Pages 199-212
Computing Affine Hulls over ${mathbb Q}$ and ${mathbb Z}$ from Sets Represented by Number Decision Diagrams….Pages 213-224
Tree Automata and XPath on Compressed Trees….Pages 225-237
Deeper Connections Between LTL and Alternating Automata….Pages 238-249
The Structure of Subword Graphs and Suffix Trees of Fibonacci Words….Pages 250-261
Observations on Determinization of Büchi Automata….Pages 262-272
The Interval Rank of Monotonic Automata….Pages 273-281
Compressing XML Documents Using Recursive Finite State Automata….Pages 282-293
Non-backtracking Top-Down Algorithm for Checking Tree Automata Containment….Pages 294-306
Size Reduction of Multitape Automata….Pages 307-318
Robust Spelling Correction….Pages 319-328
On Two-Dimensional Pattern Matching by Finite Automata….Pages 329-340
Incremental and Semi-incremental Construction of Pseudo-Minimal Automata….Pages 341-342
Is Learning RFSAs Better Than Learning DFAs?….Pages 343-344
Learning Stochastic Finite Automata for Musical Style Recognition….Pages 345-346
Simulation of Soliton Circuits….Pages 347-348
Acyclic Automata with Easy-to-Find Short Regular Expressions….Pages 349-350
On the Equivalence Problem for Programs with Mode Switching….Pages 351-352
Automata and AB-Categorial Grammars….Pages 353-355
On a Class of Bijective Binary Transducers with Finitary Description Despite Infinite State Set….Pages 356-357
Back Matter….Pages –