Implementation and Application of Automata
15th International Conference, CIAA 2010, Manitoba, Canada, August 12-15, 2010. Revised Selected Papers
Erschienen am 4. Februar 2011
XI, 332 Seiten
978-3-642-18098-9 (ISBN)
Beschreibung
This book constitutes the thoroughly refereed papers of the 15th International Conference on Implementation and Application of Automata, CIAA 2010, held in Manitoba, Winnipeg, Canada, in August 2010.
The 26 revised full papers together with 6 short papers were carefully selected from 52 submissions. The papers cover various topics such as applications of automata in computer-aided verification; natural language processing; pattern matching, data storage and retrieval; bioinformatics; algebra; graph theory; and foundational work on automata theory.
Weitere Details
Weitere Ausgaben
Andere Ausgaben
Michael Domaratzki | Kai Salomaa
Implementation and Application of Automata
15th International Conference, CIAA 2010, Manitoba, Canada, August 12-15, 2010. Revised Selected Papers
Buch
02/2011
1. Auflage
Springer
53,49 €
Versand in 5-7 Tagen
Inhalt
- Title Page
- Preface
- Organization
- Table of Contents
- Using Automata to Describe Self-Assembled Nanostructures
- A Summary of Some Discrete-Event System Control Problems
- Introduction
- Supervisory Control Problems
- Problems and Complexity
- Undecidable Problems
- Discussion
- References
- Large-Scale Training of SVMs with Automata Kernels
- Introduction
- Preliminaries
- Kernel Methods and SVM Optimization
- Overview of Kernel Methods
- Coordinate Descent Solution for SVM Optimization
- Coordinate Descent Solution for Rational Kernels
- Implementation and Analysis
- Experiments
- Conclusion
- References
- Filters for Efficient Composition of Weighted Finite-State Transducers
- Introduction
- Composition Algorithm
- Preliminaries
- Composition
- Elementary Composition Filters
- Look-Ahead Composition Filters
- Combining Filters
- Examples
- Implementation
- References
- Incremental DFA Minimisation
- Introduction
- Preliminaries
- The UNION-FIND Algorithm
- Related Work
- The Incremental Minimisation Algorithm
- Experimental Results
- Conclusions
- References
- Finite Automata for Generalized Approach to Backward Pattern Matching
- Introduction
- Historical Context
- Motivation
- Basic Definitions
- Background
- Backward Pattern Matching
- Classification of Pattern Matching Problems
- Backward Pattern Matching Machine
- Implementation Options
- Executor
- Constructor
- Construction of a Backward Pattern Matching Automaton
- Construction of a Reversed Projection Automaton
- Example: Construction of RPA for SFIERCO Problem
- Construction of Backward Pattern Matching Automaton
- Time and Space Complexity
- Conclusion
- References
- Partial Derivative Automata Formalized in Coq
- Introduction
- Regular Languages and Finite Automata
- Partial Derivative Automata
- The Coq Proof Assistant
- Formalization in Coq
- Formal Languages and Regular Expressions
- Correctness of Mirkin's Construction
- Related Work and Applications
- Concluding Remarks
- References
- Regular Geometrical Languages and Tiling the Plane
- Introduction
- Preliminaries
- Geometrical Languages
- Geometrical Languages and Tiling
- Tiling a Geometrical Figure
- Tiling the Figure of a Geometrical Language
- State Sequences Associated with the Levels of a Tiling
- Conclusion
- References
- COMPAS - A Computing Package for Synchronization
- Introduction and Motivation
- Synchronizing Automata and Synchronizing Algorithms
- COMPAS Architecture and Functionality
- References
- From Sequential Extended Regular Expressions to NFA with Symbolic Labels
- Introduction
- Regular Expressions for Property Specification
- Non-deterministic Finite Automata with Symbolic Labels
- Related Work
- Experimental Evaluation
- Conclusions and Future Work
- References
- State Complexity of Catenation Combined with Union and Intersection
- Introduction
- Preliminaries
- Catenation Combined with Union
- Catenation Combined with Intersection
- Conclusion
- References
- Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
- Introduction
- Preliminaries and Notation
- Main Results
- The NFA A
- Structure Theorem and Rational Growth
- Complexity for Testing the Regularity of Hk(L1, L2)
- References
- On Straight Words and Minimal Permutators in Finite Transformation Semigroups
- Introduction
- Straight Words
- Minimal Straight Words and Permutations of Subsets
- A Biological Example
- Conclusion
- References
- On Lazy Representations and Sturmian Graphs
- Introduction
- Continued Fraction Expansions, Sturmian Words and Sturmian Graphs
- Numeration Systems and Lazy Representations of Integers
- Ostrowski Numeration System and Lazy Representations
- Sturmian Graphs and Lazy Representations
- Conclusions
- References
- Symbolic Dynamics, Flower Automata and Infinite Traces
- Introduction
- Definitions and Notations
- Words and Traces
- Subshifts
- Infinite Traces and T-Shifts
- Flower Shifts
- References
- The Cayley-Hamilton Theorem for Noncommutative Semirings
- Introduction
- Semirings and Fields
- Permutations
- The Determinant in Noncommutative Semirings
- The Characteristic Polynomial in Noncomm. Semirings
- Multi-process CHT for Noncommutative Semirings
- Single-Process CHT for Noncommutative Semirings
- The CHT for Noncommutative Idempotent Semirings
- Conclusions
- References
- Approximating Minimum Reset Sequences
- Introduction
- Prior and Related Work
- Results
- A Simple Approximation Algorithm
- The stack cover Problem
- Open Problems and Conjectures
- References
- Transductions Computed by PC-Systems of Monotone Deterministic Restarting Automata
- Introduction
- Basic Notions and Definitions
- Transductions Computed by Restarting Automata
- Transformations Computed by PC-Systems of Monotone Deterministic RRWW-Automata
- Concluding Remarks
- References
- Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization
- Introduction
- Some Definitions and Background
- Algorithm
- An Example
- Conclusion and Future Work
- References
- Regular Expressions on Average and in the Long Run
- Introduction
- Weighted Automata on Finite and Infinite Words
- Cauchy Valuation Monoids, Cauchy Products, and Iterations
- Weighted Finite Automata and Regular Expressions
- Weighted Büchi Automata and -Regular Expressions
- Conclusion
- References
- Reachability Games on Automatic Graphs
- Introduction
- Preliminaries
- Automatic Reachability Games on Finite Arenas
- Automatic Reachability Games on Infinite Arenas
- Conclusion
- References
- Disambiguation in Regular Expression Matching via Position Automata with Augmented Transitions
- Introduction
- Formalizing the Leftmost-Longest Semantics
- Enumerating Parse Trees via Position Automata
- Correctly Nested Parenthesis Expressions
- Position NFAs with Augmented Transitions
- Developing a Matching Algorithm
- Basic Idea for Choosing the Most Prior Path
- Formalization
- Algorithm
- Related Work
- References
- A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
- Introduction
- Definitions
- Janus Automata
- Janus Automata for Pattern Languages
- Patterns with Restricted Variable Distance
- References
- A Challenging Family of Automata for Classical Minimization Algorithms
- Introduction
- Preliminaries on Automata and Moore's Minimization
- Subset Construction and Brzozowski's Algorithm
- Circular Factors of Fibonacci Words
- The Two Algorithms on Word Automata
- Further Work
- References
- State of B¨uchi Complementation
- Introduction
- Preliminaries
- Historical Review
- Comparison of Complementation Approaches
- Optimization Techniques
- For Safra-Piterman
- For Rank
- For Slice
- Experimental Results
- Conclusion
- References
- Types of Trusted Information That Make DFA Identification with Correction Queries Feasible
- Introduction
- Preliminaries
- Query Learning
- Useful Parameters for Language Learning with CQs
- Learning $k$-Injective Languages with CQs
- Concluding Remarks
- References
- Compressing Regular Expressions' DFA Table by Matrix Decomposition
- Introduction
- Related Work
- A Matrix Decomposition Method for DFA Compression
- Problem Formulation: Additive Matrix Decomposition
- Iterative Algorithm for Additive Matrix Decomposition
- Experiment and Evaluation
- Compression Efficiency Comparison
- Searching Time Comparison
- Conclusion
- References
- Relational String Verification Using Multi-track Automata
- Introduction
- String Systems
- Regular Approximation of Word Equations
- Symbolic Reachability Analysis
- Experiments
- Conclusion
- References
- A Note on a Tree-Based 2D Indexing
- Introduction
- Basic Notions
- Representation of Multidimensional Arrays for Indexing
- Tree-Based Decomposition of a Picture
- Two-Dimensional Pattern Matching in Pictures in the Tree Representation
- Pushdown Automata for Picture Indexing
- Two-Dimensional Pattern Matching Using Pushdown Automata
- Conclusion
- References
- Regular Expressions at Their Best: A Case for Rational Design
- Introduction
- Backtracking vs. Automaton-Based Implementations
- Avoiding the Construction of NFA
- Lazy Determinization
- Pathological Cases Avoided
- More Freedom of Use
- Submatching
- Efficiency and Scalability
- Design and Implementation
- ASTL, Cursors and Incrementality
- Encapsulation, Lazy Determinization, Submatches, Thread-Safety
- Performance
- Conclusion
- References
- Simulations of Weighted Tree Automata
- Introduction
- Preliminaries
- Simulation
- Category of Simulations
- Joint Reduction
- References
- Author Index
