Implementation and Application of Automata: 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings

Description

This book constitutes the thoroughly refereed papers of the 18th International Conference on Implementation and Application of Automata, CIAA 2013, held in Halifax, NS, Canada, in July 2013. The 25 revised full papers presented together with 3 invited papers and 7 short papers were carefully selected from 43 submissions. The papers cover various topics such as complexity of automata; compressed automata; counter automata; dictionary matching; edit distance; homing sequences; implementation; minimization of automata; model checking; parsing of regular expressions; partial word automata; picture languages; pushdown automata; queue automata; reachability analysis for software verification; restarting automata; transducers; tree automata; weighted automata; XML streams. Front Matter....Pages - Cover Languages and Implementations....Pages 1-1 Automata for Codes....Pages 2-15 Applications of Symbolic Finite Automata....Pages 16-23 Computing Weights....Pages 24-35 Partial Word DFAs....Pages 36-47 Using Regular Grammars for Event-Based Testing....Pages 48-59 Two-Pass Greedy Regular Expression Parsing....Pages 60-71 Universal Witnesses for State Complexity of Basic Operations Combined with Reversal....Pages 72-83 Trimming Visibly Pushdown Automata....Pages 84-96 A Uniformization Theorem for Nested Word to Word Transductions....Pages 97-108 Towards Nominal Context-Free Model-Checking....Pages 109-121 Implementation Concepts in Vaucanson 2....Pages 122-133 A Completion Algorithm for Lattice Tree Automata....Pages 134-145 Approximate Matching between a Context-Free Grammar and a Finite-State Automaton....Pages 146-157 On Palindromic Sequence Automata and Applications....Pages 158-168 LALBLC A Program Testing the Equivalence of dpda’s....Pages 169-180 Brzozowski’s Minimization Algorithm—More Robust than Expected....Pages 181-192 Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languages....Pages 193-207 On the Boundary of Regular Languages....Pages 208-219 On the Length of Homing Sequences for Nondeterministic Finite State Machines....Pages 220-231 Input-Driven Queue Automata: Finite Turns, Decidability, and Closure Properties....Pages 232-243 Hyper-optimization for Deterministic Tree Automata....Pages 244-255 Lambda-Confluence Is Undecidable for Clearing Restarting Automata....Pages 256-267 Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata....Pages 268-279 Deterministic Counter Machines and Parallel Matching Computations....Pages 280-291 Early Nested Word Automata for XPath Query Answering on XML Streams....Pages 292-305 Invertible Transducers, Iteration and Coordinates....Pages 306-318 Compressed Automata for Dictionary Matching....Pages 319-330 Enhancing Approximations for Regular Reachability Analysis....Pages 331-339 Generating Small Automata and the Černý Conjecture....Pages 340-348 Incomplete Transition Complexity of Basic Operations on Finite Languages....Pages 349-356 Back Matter....Pages -