Implementation and Application of Automata: 11th International Conference, CIAA 2006, Taipei, Taiwan, August 21-23, 2006. Proceedings

Ming Li (auth.), Oscar H. Ibarra, Hsu-Chun Yen (eds.)354037213X, 9783540372134

This book constitutes the refereed proceedings of the 11th International Conference on Implementation and Application of Automata, CIAA 2006, held in Taipei, Taiwan, in August 2006.

The 22 revised full papers and 7 revised poster papers presented together with the extended abstracts of 3 invited lectures were carefully reviewed and selected from 76 submissions. The papers cover various topics in the theory, implementation, and applications of automata and related structures.

---

Table of contents :
Front Matter….Pages –
Information Distance and Its Applications….Pages 1-9
Theory Inspired by Gene Assembly in Ciliates….Pages 10-10
On the State Complexity of Combined Operations….Pages 11-22
Path-Equivalent Removals of ε -transitions in a Genomic Weighted Finite Automaton….Pages 23-33
Hybrid Extended Finite Automata….Pages 34-45
Refinement of Near Random Access Video Coding with Weighted Finite Automata….Pages 46-57
Borders and Finite Automata….Pages 58-68
Finding Common Motifs with Gaps Using Finite Automata….Pages 69-77
Factor Oracles….Pages 78-89
Reducing Simple Grammars: Exponential Against Highly-Polynomial Time in Practice….Pages 90-101
Tiburon: A Weighted Tree Automata Toolkit….Pages 102-113
Around Hopcroft’s Algorithm….Pages 114-125
Multi-tape Automata with Symbol Classes….Pages 126-136
On the Computation of Some Standard Distances Between Probabilistic Automata….Pages 137-149
Does o-Substitution Preserve Recognizability?….Pages 150-161
Correctness Preservation and Complexity of Simple RL -Automata….Pages 162-172
Bisimulation Minimization of Tree Automata….Pages 173-185
Forgetting Automata and Unary Languages….Pages 186-197
Structurally Unambiguous Finite Automata….Pages 198-207
Symbolic Implementation of Alternating Automata….Pages 208-218
On-the-Fly Branching Bisimulation Minimization for Compositional Analysis….Pages 219-229
Finite-State Temporal Projection….Pages 230-241
Compiling Linguistic Constraints into Finite State Automata….Pages 242-252
Shift-Resolve Parsing: Simple, Unbounded Lookahead, Linear Time….Pages 253-264
A Family of Algorithms for Non Deterministic Regular Languages Inference….Pages 265-274
XSLT Version 2.0 Is Turing-Complete: A Purely Transformation Based Proof….Pages 275-276
A Finite Union of DFAs in Symbolic Model Checking of Infinite Systems….Pages 277-278
Universality of Hybrid Quantum Gates and Synthesis Without Ancilla Qudits….Pages 279-280
Reachability Analysis of Procedural Programs with Affine Integer Arithmetic….Pages 281-282
Lexical Disambiguation with Polarities and Automata….Pages 283-284
Parsing Computer Languages with an Automaton Compiled from a Single Regular Expression….Pages 285-286
Tighter Packed Bit-Parallel NFA for Approximate String Matching….Pages 287-289
Back Matter….Pages –