Implementation and Application of Automata: 7th International Conference, CIAA 2002 Tours, France, July 3–5, 2002 Revised Papers

Mehryar Mohri (auth.), Jean-Marc Champarnaud, Denis Maurel (eds.)3540403914, 9783540403913

This book constitutes the thoroughly refereed post-proceedings of the 7th International Conference on Implementation and Application of Automata, CIAA 2002, held in Tours, France, in July 2002. The 28 revised full papers presented together with an invited paper and 4 short papers were carefully selected during two rounds of reviewing and revision. The topics addressed range from theoretical and methodological issues to automata applications in software engineering, natural language processing, speech recognition, and image processing, to new representations and algorithms for efficient implementation of automata and related structures.

---

Table of contents :
Edit-Distance of Weighted Automata….Pages 1-23
p -Subsequentiable Transducers….Pages 24-34
Bidirectional Push Down Automata….Pages 35-46
Finite Automata and Non-self-Embedding Grammars….Pages 47-56
Simulation of Gate Circuits in the Algebra of Transients….Pages 57-66
The Number of Similarity Relations and the Number of Minimal Deterministic Finite Cover Automata….Pages 67-76
Regex and Extended Regex….Pages 77-84
Prime Decompositions of Regular Prefix Codes….Pages 85-94
Implementation of Dictionaries via Automata and Decision Trees….Pages 95-105
Feedback-Free Circuits in the Algebra of Transients….Pages 106-116
On Minimizing Cover Automata for Finite Languages in O ( n log n ) Time….Pages 117-127
Compilation of Constraint-Based Contextual Rules for Part-of-Speech Tagging into Finite State Transducers….Pages 128-137
Finite State Lazy Operations in NLP….Pages 138-147
State Complexity of Basic Operations on Nondeterministic Finite Automata….Pages 148-157
Adaptive Automata – A Revisited Proposal….Pages 158-168
Efficient Automaton-Based Recognition for Linear Conjunctive Languages….Pages 169-181
Syntactic Semiring and Language Equations….Pages 182-193
Reduced Power Automata….Pages 194-202
A Polynomial Time Algorithm for Left [Right] Local Testability….Pages 203-212
Whale Calf, a Parser Generator for Conjunctive Grammars….Pages 213-220
automata, a Hybrid System for Computational Automata Theory….Pages 221-227
A Package TESTAS for Checking Some Kinds of Testability….Pages 228-232
DAWG versus Suffix Array….Pages 233-238
On Predictive Parsing and Extended Context-Free Grammars….Pages 239-247
Star Normal Form, Rational Expressions, and Glushkov WFAs Properties….Pages 248-254
Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings….Pages 255-261
Term Validation of Distributed Hard Real-Time Applications….Pages 262-269
Common Subsequence Automaton….Pages 270-275
Searching for Asymptotic Error Repair….Pages 276-281
Automata-Based Representations for Arithmetic Constraints in Automated Verification….Pages 282-288
On the Implementation of Compact DAWG’s….Pages 289-294
Dynamic Programming — NFA Simulation….Pages 295-300
Deterministic Parsing of Cyclic Strings….Pages 301-306