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.
Author(s): Nataša Jonoska (auth.), Michael Domaratzki, Kai Salomaa (eds.)
Series: Lecture Notes in Computer Science 6482
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2011
Language: English
Pages: 332
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Mathematical Logic and Formal Languages; Discrete Mathematics in Computer Science; Logics and Meanings of Programs; Data Structures
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 -
