Implementation and Application of Automata: 5th International Conference, CIAA 2000 London, Ontario, Canada, July 24–25, 2000 Revised Papers

David Harel, Hillel Kugler (auth.), Shen Yu, Andrei Păun (eds.)3540424911, 9783540424918

The Fifth International Conference on Implementation and Application of – tomata (CIAA 2000) was held at the University of Western Ontario in London, Ontario, Canada on July 24-25, 2000. This conference series was formerly called the International Workshop on Implementing Automata (WIA) This volume of the Lecture Notes in Computer Science series contains all the papers that were presented at CIAA 2000, and also the abstracts of the poster papers that were displayed during the conference. The conference addressed issues in automata application and implemen- tion. The topics of the papers presented at this conference ranged from automata 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 stages of development. In the 1960s and 1970s, automata research was moti- ted heavily by problems arising from compiler construction, circuit design, string matching, etc. In recent years, many new applications have been found in various areas of computer science as well as in other disciplines. Examples of the new applications include statecharts in object-oriented modeling, nite transducers in natural language processing, and nondeterministic nite-state models in c- munication protocols. Many of the new applications do not and cannot simply apply the existing models and algorithms in automata theory to their problems.

---

Table of contents :
Synthesizing State-Based Object Systems from LSC Specifications….Pages 1-33
Applications of Finite-State Transducers in Natural Language Processing….Pages 34-46
Fast Implementations of Automata Computations….Pages 47-56
Regularly Extended Two-Way Nondeterministic Tree Automata….Pages 57-66
Glushkov Construction for Multiplicities….Pages 67-79
Implicit Structures to Implement NFA’s from Regular Expressions….Pages 80-93
New Finite Automaton Constructions Based on Canonical Derivatives….Pages 94-104
Experiments with Automata Compression….Pages 105-112
Computing Raster Images from Grid Picture Grammars….Pages 113-121
A Basis for Looping Extensions to Discriminating-Reverse Parsing….Pages 122-134
Automata for Pro-V Topologies….Pages 135-144
Reachability and Safety in Queue Systems….Pages 145-156
Generalizing the Discrete Timed Automaton….Pages 157-169
Factorization of Ambiguous Finite-State Transducers….Pages 170-181
MONA Implementation Secrets….Pages 182-194
Cursors….Pages 195-207
An Automaton Model of User-Controlled Navigation on the Web….Pages 208-216
Direct Construction of Minimal Acyclic Subsequential Transducers….Pages 217-229
Generic ε-Removal Algorithm for Weighted Automata….Pages 230-242
An O (n 2 ) Algorithm for Constructing Minimal Cover Automata for Finite Languages….Pages 243-251
Unary Language Concatenation and Its State Complexity….Pages 252-262
Implementation of a Strategy Improvement Algorithm for Finite-State Parity Games….Pages 263-271
State Complexity and Jacobsthal’s Function….Pages 272-278
A Package for the Implementation of Block Codes as Finite Automata….Pages 279-291
Regional Least-Cost Error Repair….Pages 293-301
The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata….Pages 302-310
Directly Constructing Minimal DFAs: Combining Two Algorithms by Brzozowski….Pages 311-317
The MERLin Environment Applied to ⋆-NFAs….Pages 318-326
Visual Exploration of Generation Algorithms for Finite Automata on the Web….Pages 327-328
T REEBAG ….Pages 329-330
Word Random Access Compression….Pages 331-332
Extended Sequentialization of Transducers….Pages 333-334
Lessons from INR in the Specification of Transductions….Pages 335-336
Part-of-Speech Tagging with Two Sequential Transducers….Pages 337-339
Solving Complex Problems Efficiently with Adaptive Automata….Pages 340-342