## Implementation and Application of Automata: 15th International Conference, CIAA 2010, Manitoba, Canada, August 12-15, 2010. Revised Selected PapersMichael Domaratzki, Kai Salomaa 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 |

331 | |

### Other editions - View all

### Common terms and phrases

accepting algorithm almost-equivalent alphabet B¨uchi Berlin Heidelberg 2011 binary bound Büchi automata CIAA complementation complexity component Computer Science conﬁguration construction deﬁned deﬁnition denoted deterministic diﬀerent Domaratzki eﬀective eﬃcient EQUIV-P equivalent example exists Fibonacci words ﬁlter ﬁnal ﬁnd finite ﬁnite automata ﬁrst ﬁxed given hairpin completion Heidelberg hyper-minimal idempotent implementation inﬁnite initial input integers Janus kernel labels Lemma linear LNCS matrix minimal permutator monoid multi-track DFA nondeterministic notation operations output parse trees path pattern languages pattern matching po2-Büchi automata polynomial preﬁx problem proof properties Proposition pushdown automaton queries reachability games regular expression regular languages representation reset sequence restarting Salomaa Eds satisﬁes Section semigroup semiring simulation speciﬁc Springer straight words string Sturmian graph Sturmian words subset suﬃx supervisor symbol synchronizing Theorem transducer transition function tree valuation monoid variables veriﬁcation weighted automata λ λ λ