Thomas A. Henzinger (auth.), Oscar H. Ibarra, Zhe Dang (eds.)3540405615, 9783540405610, 9781417564774
Automata theory is the foundation of computer science. Its applications have spread to almost all areas of computer science and many other disciplines. In addition, there is a growing number of software systems designed to manipulate automata, regular expressions, grammars, and related structures.
This volume contains 24 regular papers from the 8th International Conference on Implementation and Application of Automata (CIAA 2003) held in Santa Barbara, CA, USA, in July 2003 covering various topics in the theory, implementation, and application of automata and related structures. It also includes the abstracts of two invited lectures as well as the abstracts of the poster papers displayed during the conference.
Table of contents :
Automata for Specifying Component Interfaces….Pages 1-2
Automata on Words….Pages 3-11
Symbolic Synthesis of Finite-State Controllers for Request-Response Specifications….Pages 11-22
Timing Parameter Characterization of Real-Time Systems….Pages 23-34
Constructing Büchi Automata from Linear Temporal Logic Using Simulation Relations for Alternating Büchi Automata….Pages 35-48
From Regular Weighted Expressions to Finite Automata….Pages 49-60
Bideterministic Automata and Minimal Representations of Regular Languages….Pages 61-71
Succinct Descriptions of Regular Languages with Binary ⊕-NFAs….Pages 72-82
An Efficient Pre-determinization Algorithm….Pages 83-95
Introducing Vaucanson ….Pages 96-107
WFSC — A New Weighted Finite State Compiler….Pages 108-119
Ternary Directed Acyclic Word Graphs….Pages 120-130
Running Time Complexity of Printing an Acyclic Automaton….Pages 131-140
Reducing the Time Complexity of Testing for Local Threshold Testability….Pages 141-149
Branching Automata with Costs — A Way of Reflecting Parallelism in Costs….Pages 150-162
New Complexity Results for Some Linear Counting Problems Using Minimal Solutions to Linear Diophantine Equations….Pages 163-175
TCTL Inevitability Analysis of Dense-Time Systems….Pages 176-186
Conversation Protocols: A Formalism for Specification and Verification of Reactive Electronic Services….Pages 188-200
Boolean Operations for Attribute-Element Constraints….Pages 201-212
XML Schema Containment Checking Based on Semi-implicit Techniques….Pages 213-225
Weak Minimization of DFA — An Algorithm and Applications….Pages 226-238
Bag Automata and Stochastic Retrieval of Biomolecules in Solution….Pages 239-250
An Optimal Algorithm for Maximum-Sum Segment and Its Application in Bioinformatics….Pages 251-257
Robust Parsing Using Dynamic Programming….Pages 258-268
LR Parsing for Global Index Languages (GILs)….Pages 269-281
The Ehrenfeucht-Mycielski Sequence….Pages 282-293
The Longest Common Subsequence Problem A Finite Automata Approach….Pages 294-296
AVA: An Applet for Visualizing FRACTRAN and Other Automata….Pages 297-298
Preliminary Experiments in Hardcoding Finite Automata….Pages 299-300
Computational Linguistic Motivations for a Finite-State Machine Hierarchy….Pages 301-303
The Effect of Rewriting Regular Expressions on Their Accepting Automata….Pages 304-306
Building Context-Sensitive Parsers from CF Grammars with Regular Control Language….Pages 306-308
Finite-State Molecular Computing….Pages 309-310
Reviews
There are no reviews yet.