Implementation and Application of Automata: 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings

Description

This book constitutes the thoroughly refereed papers of the 17th International Conference on Implementation and Application of Automata, CIAA 2012, held in Porto, Portugal, in July 2012. The 21 revised full papers presented together with 5 invited papers and 7 short papers were carefully selected from 53 submissions. The papers cover various topics such as automata applications in formal verification methods, natural language processing, pattern matching, data storage and retrieval, and bioinformatics, as well as theoretical work on automata theory. Front Matter....Pages - In Memoriam Sheng Yu....Pages 1-4 In Search of Most Complex Regular Languages....Pages 5-24 A Formal Framework for Processes Inspired by the Functioning of Living Cells....Pages 25-27 Adding Pebbles to Weighted Automata....Pages 28-51 Typed Linear Algebra for Weigthed (Probabilistic) Automata....Pages 52-65 A Pushdown Transducer Extension for the OpenFst Library....Pages 66-77 Weak Inclusion for Recursive XML Types....Pages 78-89 Synchronizing Automata on Quasi-Eulerian Digraph....Pages 90-100 Cellular Automata on Regular Rooted Trees....Pages 101-112 Strict Local Testability with Consensus Equals Regularity....Pages 113-124 Nominal Automata for Resource Usage Control....Pages 125-137 Weighted Nested Word Automata and Logics over Strong Bimonoids....Pages 138-148 A Fast Suffix Automata Based Algorithm for Exact Online String Matching....Pages 149-158 P(l)aying for Synchronization....Pages 159-170 Synchronizing Automata of Bounded Rank....Pages 171-179 Automatic Theorem-Proving in Combinatorics on Words....Pages 180-191 How to Synchronize the Heads of a Multitape Automaton....Pages 192-204 Regular Ideal Languages and Their Boolean Combinations....Pages 205-216 Hyper-minimization for Deterministic Tree Automata....Pages 217-228 On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs....Pages 229-239 Implementing Computations in Automaton (Semi)groups....Pages 240-252 On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata....Pages 253-264 A Disambiguation Algorithm for Finite Automata and Functional Transducers....Pages 265-277 Synchronization of Automata with One Undefined or Ambiguous Transition....Pages 278-288 Restarting Tiling Automata....Pages 289-300 Crossing the Syntactic Barrier: Hom-Disequalities for ${\mathcal H}_1$ -Clauses....Pages 301-312 Factor and Subsequence Kernels and Signatures of Rational Languages....Pages 313-320 Multi-Tilde-Bar Derivatives....Pages 321-328 On Positive TAGED with a Bounded Number of Constraints....Pages 329-336 SDFA: Series DFA for Memory-Efficient Regular Expression Matching....Pages 337-344 The Removal of Weighted ε -Transitions....Pages 345-352 Weighted LTL with Discounting....Pages 353-360 Automata with Modulo Counters and Nondeterministic Counter Bounds....Pages 361-368 Back Matter....Pages -