CIAA 2003, Volume 7

Front Cover
Springer Science & Business Media, Jun 23, 2003 - Computers - 306 pages
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.
 

Contents

EditDistance of Weighted Automata
1
pSubsequentiable Transducers
24
Bidirectional Push Down Automata
35
Finite Automata and NonselfEmbedding Grammars
47
Simulation of Gate Circuits in the Algebra of Transients
57
The Number of Similarity Relations and the Number of Minimal Deterministic Finite Cover Automata
67
Regex and Extended Regex
77
Prime Decompositions of Regular Prefix Codes
85
A Polynomial Time Algorithm for Left Right Local Testability
203
Whale Calf a Parser Generator for Conjunctive Grammars
213
automata a Hybrid System for Computational Automata Theory
221
A Package TESTAS for Checking Some Kinds of Testability
228
DAWG versus Suffix Array
233
On Predictive Parsing and Extended ContextFree Grammars
239
Star Normal Form Rational Expressions and Glushkov WFAs Properties
248
Comparison of Construction Algorithms for Minimal Acyclic Deterministic FiniteState Automata from Sets of Strings
255

Implementation of Dictionaries via Automata and Decision Trees
95
FeedbackFree Circuits in the Algebra of Transients
106
On Minimizing Cover Automata for Finite Languages in On log n Time
117
Compilation of ConstraintBased Contextual Rules for PartofSpeech Tagging into Finite State Transducers
128
Finite State Lazy Operations in NLP
138
State Complexity of Basic Operations on Nondeterministic Finite Automata
148
Adaptive Automata A Revisited Proposal
158
Efficient AutomatonBased Recognition for Linear Conjunctive Languages
169
Syntactic Semiring and Language Equations
182
Reduced Power Automata
194
Term Validation of Distributed Hard RealTime Applications
262
Common Subsequence Automaton
270
Searching for Asymptotic Error Repair
276
AutomataBased Representations for Arithmetic Constraints in Automated Verification
282
On the Implementation of Compact DAWGs
289
Dynamic Programming NFA Simulation
295
Deterministic Parsing of Cyclic Strings
301
Author Index
307
Copyright

Other editions - View all

Common terms and phrases