Implementation and Application of Automata: 8th International Conference, Ciaa 2003, Santa Barbara, Ca, Usa, July 16-18, 2003 : Proceedings

by Ciaa 2003 (2003 Santa Barbara, Calif.); Ibarra, Oscar H.; Danga, Zhe; Dang, Zhe

• ISBN13: 9783540405610
• ISBN10: 3540405615
• Format: Paperback
• Copyright: 2003-08-01
• Publisher: Springer-Verlag New York Inc

Summary

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	p. 1
Automata on Words	p. 3
Symbolic Synthesis of Finite-State Controllers for Request-Response Specifications	p. 11
Timing Parameter Characterization of Real-Time Systems	p. 23
Constructing Buchi Automata from Linear Temporal Logic Using Simulation Relations for Alternating Buchi Automata	p. 35
From Regular Weighted Expressions to Finite Automata	p. 49
Bideterministic Automata and Minimal Representations of Regular Languages	p. 61
Succinct Descriptions of Regular Languages with Binary [actual symbol not reproducible]-NFAs	p. 72
An Efficient Pre-determinization Algorithm	p. 83
Introducing Vaucanson	p. 96
WFSC - A New Weighted Finite State Compiler	p. 108
Ternary Directed Acyclic Word Graphs	p. 120
Running Time Complexity of Printing an Acyclic Automaton	p. 131
Reducing the Time Complexity of Testing for Local Threshold Testability	p. 141
Branching Automata with Costs - A Way of Reflecting Parallelism in Costs	p. 150
New Complexity Results for Some Linear Counting Problems Using Minimal Solutions to Linear Diophantine Equations	p. 163
TCTL Inevitability Analysis of Dense-Time Systems	p. 176
Conversation Protocols: A Formalism for Specification and Verification of Reactive Electronic Services	p. 188
Boolean Operations for Attribute-Element Constraints	p. 201
XML Schema Containment Checking Based on Semi-implicit Techniques	p. 213
Weak Minimization of DFA - An Algorithm and Applications	p. 226
Bag Automata and Stochastic Retrieval of Biomolecules in Solution	p. 239
An Optimal Algorithm for Maximum-Sum Segment and Its Application in Bioinformatics Extended Abstract	p. 251
Robust Parsing Using Dynamic Programming	p. 258
LR Parsing for Global Index Languages (GILs)	p. 269
The Ehrenfeucht-Mycielski Sequence	p. 282
The Longest Common Subsequence Problem - A Finite Automata Approach	p. 294
AVA: An Applet for Visualizing FRACTRAN and Other Automata	p. 297
Preliminary Experiments in Hardcoding Finite Automata	p. 299
Computational Linguistic Motivations for a Finite-State Machine Hierarchy	p. 301
The Effect of Rewriting Regular Expressions on Their Accepting Automata	p. 304
Building Context-Sensitive Parsers from CF Grammars with Regular Control Language	p. 306
Finite-State Molecular Computing	p. 309
Author Index	p. 311
Table of Contents provided by Blackwell. All Rights Reserved.