Implementation and Application of Automata: 6th International Conference, CIAA 2001 Pretoria, South Africa, July 23–25, 2001 Revised Papers

Iñaki Alegria, Maxux Aranzabe, Nerea Ezeiza (auth.), Bruce W. Watson, Derick Wood (eds.)3540004009, 9783540004004

This book constitutes the thoroughly refereed post-proceedings of the 6th International Conference on Implementation and Application of Automata, CIAA 2001, held in Pretoria, South Africa in July 2001.

The 23 revised full papers presented together with an invited paper were carefully selected during two rounds of reviewing and revision. The topics addressed from theoretical as well as application-oriented viewpoints range from foundational and methodological issues to novel applications in object-oriented modeling, finite transducers in natural language processing, and non-deterministic finite-state models in communication protocols.

---

Table of contents :
Using Finite State Technology in Natural Language Processing of Basque….Pages 1-12
Cascade Decompositions are Bit-Vector Algorithms….Pages 13-26
Submodule Construction and Supervisory Control: A Generalization….Pages 27-39
Counting the Solutions of Presburger Equations without Enumerating Them….Pages 40-51
Brzozowski’s Derivatives Extended to Multiplicities….Pages 52-64
Finite Automata for Compact Representation of Language Models in NLP….Pages 65-73
Past Pushdown Timed Automata….Pages 74-86
Scheduling Hard Sporadic Tasks by Means of Finite Automata and Generating Functions….Pages 87-100
Bounded-Graph Construction for Noncanonical Discriminating-Reverse Parsers….Pages 101-114
Finite-State Transducer Cascade to Extract Proper Names in Texts….Pages 115-124
Is this Finite-State Transducer Sequentiable?….Pages 125-134
Compilation Methods of Minimal Acyclic Finite-State Automata for Large Dictionaries….Pages 135-148
Bit Parallelism – NFA Simulation….Pages 149-160
Improving Raster Image Run-Length Encoding Using Data Order….Pages 161-176
Enhancements of Partitioning Techniques for Image Compression Using Weighted Finite Automata….Pages 177-189
Extraction of ε-Cycles from Finite-State Transducers….Pages 190-201
On the Size of Deterministic Finite Automata….Pages 202-213
Crystal Lattice Automata….Pages 214-220
Minimal Adaptive Pattern-Matching Automata for Efficient Term Rewriting….Pages 221-233
Adaptive Rule-Driven Devices – General Formulation and Case Study….Pages 234-250
Typographical Nearest-Neighbor Search in a Finite-State Lexicon and Its Application to Spelling Correction….Pages 251-260
On the Software Design of Cellular Automata Simulators for Ecological Modeling….Pages 261-262
Random Number Generation with ⊕-NFAs….Pages 263-273
Supernondeterministic Finite Automata….Pages 274-288