Implementation and Application of Automata
16th International Conference, CIAA 2011, Blois, France, July 13-16, 2011, Revised Selected Papers
Erschienen am 5. Juli 2011
XIII, 299 Seiten
978-3-642-22256-6 (ISBN)
Beschreibung
This book constitutes the thoroughly refereed papers of the 16th International Conference on Implementation and Application of Automata, CIAA 2011, held in Blois, France, in July 2011.
The 20 revised full papers together with 4 short papers were carefully selected from 38 submissions. The papers cover various topics such as applications of automata in computer-aided verification; natural language processing; pattern matching, data storage and retrieval; document engineering and bioinformatics as well as foundational work on automata theory.
Weitere Details
Weitere Ausgaben
Andere Ausgaben
Béatrice Bouchou-Markhoff | Pascal Caron | Jean-Marc Champarnaud
Implementation and Application of Automata
16th International Conference, CIAA 2011, Blois, France, July 13-16, 2011, Revised Selected Papers
Buch
07/2011
1. Auflage
Springer
53,49 €
Versand in 7-9 Tagen
Inhalt
- Title
- Preface
- Organization
- Table of Contents
- Invited Lectures
- Derick Wood: Always in Our Hearts
- References
- Streamable Fragments of Forward XPath
- Introduction
- FXP
- Deterministic Automata for XML Streams
- FXP to Deterministic Automata
- Streamability of Query Languages
- Related Work
- Conclusion
- References
- Gaining Power by Input Operations: Finite Automata and Beyond
- Introduction
- Extended Finite Automata
- Computational Capacity
- Extended Pushdown Automata
- Conclusions
- References
- Technical Contributions
- Weak Inclusion for XML Types
- Introduction
- Preliminaries
- Weak Inclusion for Regular Tree Grammars
- Experimental Results
- The Special Case of Deterministic DTDs
- Conclusion
- References
- Categorial Grammars with Iterated Types form a Strict Hierarchy of k-Valued Languages
- Introduction
- Background
- Categorial Grammars
- *AB Calculus
- Abstract Automata Equivalent to CDG
- Deduction Structures
- F-A Structures over a Set E
- Functor-Argument Structures with Iterated Subtypes
- A Strict Hierarchy
- Overview
- Order 1 and Iteration
- Order &1 and Iteration
- Conclusion
- References
- Bouma2 - A High-Performance Input-Aware Multiple String-Match Algorithm
- Introduction
- Related Work
- Basic Definitions
- Traces and Motifs
- Resolve-Sets
- The Bouma2 Compilation Process
- Cost Functions
- The Bouma2 Compilation Graph
- The Bouma2 Match Process
- The Match Structures
- Match-Time Algorithm
- The Resolve Process
- The Resolve Dimension
- Experimental Results
- Extensions and Future Work
- References
- Random Generation of Deterministic Acyclic Automata Using Markov Chains
- Introduction
- Notations
- Markov Chains and Random Generation
- Algorithm
- Proofs
- Minimal Acyclic Automata
- Experiments
- Conclusion
- References
- Variable and Clause Ordering in an FSA Approach to Propositional Satisfiability
- Introduction
- Definitions
- Satisfiability as FSA Construction
- Variable and Clause Ordering Heuristics
- Experimentation
- Tool and Setting
- Initial Experiments
- Hard Benchmarks Experiments
- Conclusions and Future Work
- References
- Nondeterministic Moore Automata and Brzozowski's Algorithm
- Introduction
- Nondeterministic Moore Automata
- A Variant of Brzozowski's Algorithm on Nondeterministic Moore Automata
- Conclusions and Further work
- References
- Building Phylogeny with Minimal Absent Words
- Introduction
- Basic Definition
- Method
- Minimal Absent Words Trie Computation
- Similarity/Dissimilarity Measures
- Results and Discussion
- Minimal Absent Words Trie Computation
- Phylogeny Building from Minimal Absent Words
- Conclusion
- References
- On the Hardness of Priority Synthesis
- Introduction
- Example: Simple BIP Models
- Formulating BIP Models and Priority Synthesis Based on Transition Systems
- Priority Synthesis Is NP-Complete
- Discussion
- References
- Smaller Representation of Finite State Automata
- Introduction
- Motivation and Goals
- Test Data
- Size Reduction Techniques
- Experiments and Results
- Conclusions
- References
- Compositional Failure Detection in Structured Transition Systems
- Introduction
- Technical Preliminaries
- Products of Transition Systems
- Automata
- Composition: Simple Case
- Extension to Specifications with Predicates
- Further Results and Conclusion
- References
- Chrobak Normal Form Revisited, with Applications
- Introduction
- Preliminaries
- The Algorithm
- Application to Regular Expressions Conversion
- Application to Context-Free Grammar Conversion
- References
- A Cellular Automaton Model for Car Traffic with a Form-One-Lane Rule
- Introduction
- CA-Based Traffic Simulation Models
- Form-One-Lane Rule Model
- Experiments and Analysis
- Single-Lane Model and the Proposed Model
- The Traffic Flux with a Junction
- The Length of Traffic Jam
- Applications of the Proposed Model
- Conclusions
- References
- Loops and Overloops for Tree Walking Automata
- Introduction
- Loops, Overloops and the Membership Problem
- Transforming TWA into Equivalent BUTA
- Two Variants: Loops and Overloops
- Overloops and the Deterministic Case
- The Emptiness Problem and Experimental Results
- Conclusion
- References
- Nondeterministic State Complexity of Star-Free Languages
- Introduction
- Preliminaries
- Results on the Operation Problem
- References
- On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs
- Introduction
- Undecidability of Containment and Equivalence
- Output Finite-Valued NFTs
- Right-Bounded LCFGs
- Output/Input Finite-Valued NFTs
- Right/Left-Bounded LCFGs
- Generalizations
- References
- Computing All l-Cover Automata Fast
- Introduction
- Preliminaries
- Gap-Trees
- Computing a Gap-Tree
- References
- Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines
- Towards More Expressive 2D Deterministic Automata
- Introduction
- Preliminaries
- Tiling Recognizable Picture Languages
- 2D Automata Models
- Adding Expressivity
- Properties of 4-Way Deterministic Wang Automata
- References
- Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata
- Introduction
- Cyclic Automata
- Eulerian Automata
- Conclusion and Conjectures
- References
- Distributed Event Clock Automata
- Introduction
- Preliminaries
- Models of Time
- Clo cks
- Automata Background
- Timed Automata
- Timed Automata with Independent Clocks
- Recursive Event Clocks Automata
- Timed Languages
- Timed Languages of icTA
- Distributed Event Clock Automata
- Timed Languages of DECA
- Recursive Distributed Event Clocks Temporal Logic
- Syntax
- Semantics
- Decidability
- Extensions
- Conclusions
- References
- Short Papers
- Fly-Automata, Their Properties and Applications
- Introduction
- Preliminaries: Terms
- Application Domain
- Graphs as Logical Structures
- Term Representation of Graphs of Bounded Clique-Width
- Term Automata
- Finite Bottom-Up Term Automata
- Infinite (Bottom-up) Term Automata
- Fly Term Automata
- Implementation of Fly-Automata
- Experiments
- Conclusion and Perspectives
- References
- Tree Template Matching in Ranked Ordered Trees by Pushdown Automata
- Introduction
- Preliminaries
- Basic Definitions
- Properties of Trees in Postfix Notation
- Problem Definition
- Algorithm
- Match-Sets
- Computing Match-Sets
- The Algorithm
- Conclusion
- References
- Information Extraction from Semi-structured Resources: A Two-Phase Finite State Transducers Approach
- Introduction
- Finite State Transducers in NLP
- Resources and Tools Used
- Software System for Linguistic Tasks
- Semi-structured Resource: Encyclopedia
- The Two Phase FST Method
- The First Phase: Creating Records of Data
- The Second Phase: Extracting Particular Attributes
- Results and Evaluation of the Method
- Conclusion
- References
- Experimental Study of the Shortest Reset Word of Random Automata
- Introduction
- Solving Automata Synchronization Problem via Reduction to SAT
- Random Automaton
- Experimental Results
- Conclusion and Discussion
- References
- Author Index
