Implementation and Application of Automata: 7th International Conference, CIAA 2002, Tours, France, July 3-5, 2002, Revised Papers (Lecture Notes in Computer Science)

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. The 7th International Conference On Implementation And Application Of Au- Mata (ciaa 2002) Was Held At The Universit ́ E Fran ̧ Cois Rabelais Of Tours, In Tours, France, On July 3–5, 2002. This Volume Of Lecture Notes In Computer Science Contains All The Papers That Were Presented At Ciaa 2002, As Well As The Abstracts Of The Poster Papers That Were Displayed During The Conference. The Conference Addressed Issues In Automata Application And Implemen- Tion. Thetopicsofthepaperspresentedinthisconferencerangedfromautomata Applications In Software Engineering, Natural Language And Speech Recognition, And Image Processing, To New Representations And Algorithms For E?cient Imp- Mentation Of Automata And Related Structures. Automata Theory Is One Of The Oldest Areas In Computer Science. Research In Automata Theory Has Always Been Motivated By Its Applications Since Its Early Stage Of Development. In The 1960s And 1970s, Automata Research Was Motivated Heavily By Problems Arising From Compiler Construction, Circuit Design, String Matching, Etc. In Recent Years, Many New Applications Of Automata Have Been Found In Various Areas Of Computer Science As Well As In Other Disciplines. - Amples Of The New Applications Include Statecharts In Object-oriented Modeling, ?nite Transducers In Natural Language Processing, And Nondeterministic ?ni- State Models In Communication Protocols. Many Of The New Applications Cannot Simply Utilize The Existing Models And Algorithms In Automata Theory In The - Lution To Their Problems. New Models, Or Modi?cations Of The Existing Models, Are Needed To Satisfy Their Requirements. Edit-distance Of Weighted Automata / Mehryar Mohri -- P-subsequentiable Transducers / Cyril Allauzen And Mehryar Mohri -- Bidirectional Push Down Automata / Miguel A. Alonso, Victor J. Diaz And Manuel Vilares -- Finite Automata And Non-self-embedding Grammars / Marcella Anselmo, Dora Giammarresi And Stefano Varricchio -- Simulation Of Gate Circuits In The Algebra Of Transients / Janusz Brzozowski And Mihaela Gheorghiu -- The Number Of Similarity Relations And The Number Of Minimal Deterministic Finite Cover Automata / Cezar Campeanu And Andrei Paun -- Regex And Extended Regex / Cezar Campeanu, Kai Salomaa And Sheng Yu -- Prime Decompositions Of Regular Prefix Codes / Jurek Czyzowicz, Wojciech Fraczak, Andrzej Pelc And Wojciech Rytter. Jean-marc Champarnaud, Denis Maurel (eds.). Includes Bibliographical References And Index. 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 Implementation and Application of Automata: 7th International Conference, CIAA 2002 Tours, France, July 3–5, 2002 Revised Papers Author: Jean-Marc Champarnaud, Denis Maurel Published by Springer Berlin Heidelberg ISBN: 978-3-540-40391-3 DOI: 10.1007/3-540-44977-9 Table of Contents: Edit-Distance of Weighted Automata p-Subsequentiable Transducers Bidirectional Push Down Automata Finite Automata and Non-self-Embedding Grammars Simulation of Gate Circuits in the Algebra of Transients The Number of Similarity Relations and the Number of Minimal Deterministic Finite Cover Automata Regex and Extended Regex Prime Decompositions of Regular Prefix Codes Implementation of Dictionaries via Automata and Decision Trees Feedback-Free Circuits in the Algebra of Transients On Minimizing Cover Automata for Finite Languages in O(n log n) Time Compilation of Constraint-Based Contextual Rules for Part-of-Speech Tagging into Finite State Transducers Finite State Lazy Operations in NLP State Complexity of Basic Operations on Nondeterministic Finite Automata Adaptive Automata - A Revisited Proposal Efficient Automaton-Based Recognition for Linear Conjunctive Languages Syntactic Semiring and Language Equations Reduced Power Automata A Polynomial Time Algorithm for Left [Right] Local Testability Whale Calf, a Parser Generator for Conjunctive Grammars The edit-distance of two strings is the minimal cost of a sequence of symbol insertions, deletions, or substitutions transforming one string into the other [18].