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

Front Cover
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Synthesizing StateBased Object Systems from LSC Specifications
1
Applications of FiniteState Transducers in Natural Language Processing
34
Fast Implementations of Automata Computations
47
Regularly Extended TwoWay Nondeterministic Tree Automata
57
Glushkov Construction for Multiplicities
67
Implicit Structures to Implement NFAs from Regular Expressions
80
New Finite Automaton Constructions Based on Canonical Derivatives
94
Experiments with Automata Compression
105
An On2 Algorithm for Constructing Minimal Cover Automata for Finite Languages
243
Unary Language Concatenation and Its State Complexity
252
Implementation of a Strategy Improvement Algorithm for FiniteState Parity Games
263
State Complexity and Jacobsthals Function
272
A Package for the Implementation of Block Codes as Finite Automata
279
Regional LeastCost Error Repair
293
The Parameterized Complexity of Intersection and Composition Operations on Sets of FiniteState Automata
302
Combining Two Algorithms by Brzozowski
311

Computing Raster Images from Grid Picture Grammars
113
A Basis for Looping Extensions to DiscriminatingReverse Parsing
122
Automata for ProV Topologies
135
Reachability and Safety in Queue Systems
145
Generalizing the Discrete Timed Automaton
157
Factorization of Ambiguous FiniteState Transducers
170
MONA Implementation Secrets
182
Cursors
195
An Automaton Model of UserControlled Navigation on the Web
208
Direct Construction of Minimal Acyclic Subsequential Transducers
217
Generic Removal Algorithm for Weighted Automata
230
The MERLin Environment Applied to NFAs
318
Visual Exploration of Generation Algorithms for Finite Automata on the Web
327
TREEBAG
329
Word Random Access Compression
331
Extended Sequentialization of Transducers
333
Lessons from INR in the Specification of Transductions
335
PartofSpeech Tagging with Two Sequential Transducers
337
Solving Complex Problems Efficiently with Adaptive Automata
340
Author Index
343
Copyright

Other editions - View all

Common terms and phrases