Implementation and Application of Automata

Name: Implementation and Application of Automata | 15th International Conference, CIAA 2010, Manitoba, Canada, August 12-15, 2010. Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

15th International Conference, CIAA 2010, Manitoba, Canada, August 12-15, 2010. Revised Selected Papers

Michael Domaratzki Kai Salomaa(Herausgeber*in)

Springer (Verlag)

Erschienen am 4. Februar 2011

XI, 332 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-18098-9 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

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

Systemvoraussetzungen

Als PDF speichern Als Link merken