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

Front Cover
Michael Domaratzki, Kai Salomaa
Springer Science & Business Media, Feb 4, 2011 - Computers - 332 pages

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.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Using Automata to Describe SelfAssembled Nanostructures
1
A Summary of Some DiscreteEvent System Control Problems
4
LargeScale Training of SVMs with Automata Kernels
17
Filters for Efficient Composition of Weighted FiniteState Transducers
28
Incremental DFA Minimisation
39
Finite Automata for Generalized Approach to Backward Pattern Matching
49
Partial Derivative Automata Formalized in Coq
59
Regular Geometrical Languages and Tiling the Plane
69
Transductions Computed by PCSystems of Monotone Deterministic Restarting Automata
163
Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization
173
Regular Expressions on Average and in the Long Run
211
Reachability Games on Automatic Graphs
222
Disambiguation in Regular Expression Matching via Position Automata with Augmented Transitions
231
A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
241
A Challenging Family of Automata for Classical Minimization Algorithms
251
State of Buchi Complementation
261

COMPAS A Computing Package for Synchronization
79
From Sequential Extended Regular Expressions to NFA with Symbolic Labels
87
State Complexity of Catenation Combined with Union and Intersection
95
Complexity Results and the Growths of Hairpin Completions of Regular Languages Extended Abstract
105
On Straight Words and Minimal Permutators in Finite Transformation Semigroups
115
On Lazy Representations and Sturmian Graphs
125
Symbolic Dynamics Flower Automata and Infinite Traces
135
The CayleyHamilton Theorem for Noncommutative Semirings
143
Approximating Minimum Reset Sequences
154
Types of Trusted Information That Make DFA Identification with Correction Queries Feasible
272
Compressing Regular Expressions DFA Table by Matrix Decomposition
282
Relational String Verification Using Multitrack Automata
290
A Note on a TreeBased 2D Indexing
300
A Case for Rational Design
310
Simulations of Weighted Tree Automata
321
Author Index
331
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information