Implementation and Application of Automata: 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings (Lecture Notes in Computer Science Book 9705)

This book constitutes the refereed proceedings of the 21st International Conference on Implementation and Application of Automata, CIAA 2016, held in Seoul, South Korea, in July 2016. The 26 revised full papers presented were carefully reviewed and selected from 49 submissions. The papers cover a wide range of topics including characterizations of automata, computing distances between strings and languages, implementations of automata and experiments, enhanced regular expressions, and complexity analysis. Front Matter....Pages I-XVI Front Matter....Pages 1-1 Decision Problems for Finite Automata over Infinite Algebraic Structures....Pages 3-11 Front Matter....Pages 13-13 The Degree of Irreversibility in Deterministic Finite Automata....Pages 15-26 Deterministic Stack Transducers....Pages 27-38 Computing the Expected Edit Distance from a String to a PFA....Pages 39-50 Derived-Term Automata of Multitape Rational Expressions....Pages 51-63 Solving Parity Games Using an Automata-Based Algorithm....Pages 64-76 Ternary Equational Languages....Pages 77-88 Problems on Finite Automata and the Exponential Time Hypothesis....Pages 89-100 A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata....Pages 101-112 A Practical Simulation Result for Two-Way Pushdown Automata....Pages 113-124 Nondeterministic Complexity of Operations on Closed and Ideal Languages....Pages 125-137 On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L....Pages 138-149 Kuratowski Algebras Generated by Prefix-Free Languages....Pages 150-162 A Logical Characterization of Small 2NFAs....Pages 163-175 Experiments with Synchronizing Automata....Pages 176-188 Implementation of Code Properties via Transducers....Pages 189-201 On Synchronizing Automata and Uniform Distribution....Pages 202-212 Looking for Pairs that Hard to Separate: A Quantum Approach....Pages 213-223 Prefix Distance Between Regular Languages....Pages 224-235 Complexity of Sets of Two-Dimensional Patterns....Pages 236-247 Front Matter....Pages 13-13 The Complexity of Fixed-Height Patterned Tile Self-assembly....Pages 248-259 Derivative-Based Diagnosis of Regular Expression Ambiguity....Pages 260-272 Regular Approximation of Weighted Linear Nondeleting Context-Free Tree Languages....Pages 273-284 Derivatives for Enhanced Regular Expressions....Pages 285-297 Weighted Restarting Automata as Language Acceptors....Pages 298-309 Enhancing Practical TAG Parsing Efficiency by Capturing Redundancy....Pages 310-321 Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA....Pages 322-334 Back Matter....Pages 335-335