CIAA 2003, Volume 7The 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 |
307 | |
Other editions - View all
Implementation and Application of Automata: 7th International Conference ... Jean-Marc Champarnaud,Denis Maurel No preview available - 2014 |
Common terms and phrases
accepted acyclic adaptive actions algorithm alphabet application automaton Berlin Heidelberg 2003 Boolean Champarnaud CIAA complexity Computer Science conjunctive grammars construction context-free grammars corresponding D-articulation DAWG decomposition defined definition denote deterministic finite deterministic finite automaton edit-distance equivalent example extended regex finite finite automata finite languages finite-state given Glushkov idempotent implementation initial input string input symbol integer Kleene star Lemma length level(p LNCS locally idempotent locally testable log semiring matching Maurel Eds minimal DFCA node non-deterministic NSE grammars operations output p-subsequential pair parser parsing partial syntax tree path prefix code Proof pushdown store reachable regular expressions regular language representation resp result SCC-node semigroup sequence simulation Springer-Verlag Berlin Heidelberg suffix array syntactic semiring tags terminal Theorem transients transition graph transition semigroup tropical semiring tuple variables weighted automata weighted transducers word