Implementation and Application of Automata: 15th International Conference, CIAA 2010, Winnipeg, MB, Canada, August 12-15, 2010. Revised Selected Papers

Front Matter....Pages -
Using Automata to Describe Self-Assembled Nanostructures....Pages 1-3
A Summary of Some Discrete-Event System Control Problems....Pages 4-16
Large-Scale Training of SVMs with Automata Kernels....Pages 17-27
Filters for Efficient Composition of Weighted Finite-State Transducers....Pages 28-38
Incremental DFA Minimisation....Pages 39-48
Finite Automata for Generalized Approach to Backward Pattern Matching....Pages 49-58
Partial Derivative Automata Formalized in Coq ....Pages 59-68
Regular Geometrical Languages and Tiling the Plane....Pages 69-78
COMPAS - A Computing Package for Synchronization....Pages 79-86
From Sequential Extended Regular Expressions to NFA with Symbolic Labels....Pages 87-94
State Complexity of Catenation Combined with Union and Intersection....Pages 95-104
Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)....Pages 105-114
On Straight Words and Minimal Permutators in Finite Transformation Semigroups....Pages 115-124
On Lazy Representations and Sturmian Graphs....Pages 125-134
Symbolic Dynamics, Flower Automata and Infinite Traces....Pages 135-142
The Cayley-Hamilton Theorem for Noncommutative Semirings....Pages 143-153
Approximating Minimum Reset Sequences....Pages 154-162
Transductions Computed by PC-Systems of Monotone Deterministic Restarting Automata....Pages 163-172
Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization....Pages 173-180
Partially Ordered Two-Way Büchi Automata....Pages 181-190
Two-Party Watson-Crick Computations....Pages 191-200
Better Hyper-minimization....Pages 201-210
Regular Expressions on Average and in the Long Run....Pages 211-221
Reachability Games on Automatic Graphs....Pages 222-230
Disambiguation in Regular Expression Matching via Position Automata with Augmented Transitions....Pages 231-240
A Polynomial Time Match Test for Large Classes of Extended Regular Expressions....Pages 241-250
A Challenging Family of Automata for Classical Minimization Algorithms....Pages 251-260
State of Büchi Complementation....Pages 261-271
Types of Trusted Information That Make DFA Identification with Correction Queries Feasible....Pages 272-281
Compressing Regular Expressions’ DFA Table by Matrix Decomposition....Pages 282-289
Relational String Verification Using Multi-track Automata....Pages 290-299
A Note on a Tree-Based 2D Indexing....Pages 300-309
Regular Expressions at Their Best: A Case for Rational Design....Pages 310-320
Simulations of Weighted Tree Automata....Pages 321-330
Back Matter....Pages -