Implementation and Application of Automata: 20th International Conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings (Lecture Notes in Computer Science Book 9223)

This book constitutes the refereed proceedings of the 20th International Conference on Implementation and Application of Automata, CIAA 2015, held in held in Umeå, Sweden, in August 2015. The 22 revised full papers presented together with 4 invited papers and 2 toool demonstration papers were carefully reviewed and selected from 49 submissions. The papers cover all aspects of cover automata, counter automata, decision algorithms on automata, descriptional complexity, expressive power of automata, homing sequences, jumping finite automata, multi-dimensional languages, parsing and pattern matching, quantum automata, realtime pushdown automata, random generation of automata, regular expressions, security issues, sensors in automata, transducers, transformation of automata, and weighted automata. Front Matter....Pages I-XXIII Front Matter....Pages 1-1 Automata and Logics for Concurrent Systems: Five Models in Five Pages....Pages 3-12 Hardware Implementations of Finite Automata and Regular Expressions....Pages 13-17 Front Matter....Pages 19-19 Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems....Pages 21-34 From Ambiguous Regular Expressions to Deterministic Parsing Automata....Pages 35-48 Deciding Synchronous Kleene Algebra with Derivatives....Pages 49-62 On the Hierarchy of Block Deterministic Languages....Pages 63-75 Security of Numerical Sensors in Automata....Pages 76-88 Jumping Finite Automata: Characterizations and Complexity....Pages 89-101 Run-Length Encoded Nondeterministic KMP and Suffix Automata....Pages 102-113 More on Deterministic and Nondeterministic Finite Cover Automata....Pages 114-126 On the Number of Synchronizing Colorings of Digraphs....Pages 127-139 On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism....Pages 140-152 Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata....Pages 153-164 Subword Metrics for Infinite Words....Pages 165-175 From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods....Pages 176-187 Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata....Pages 188-198 Expressive Capacity of Concatenation Freeness....Pages 199-210 The Membership Problem for Linear and Regular Permutation Languages....Pages 211-223 Classical and Quantum Counter Automata on Promise Problems....Pages 224-237 State Complexity of Prefix Distance....Pages 238-249 Front Matter....Pages 19-19 (Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars....Pages 250-262 On the Disambiguation of Weighted Automata....Pages 263-278 Checking Whether an Automaton Is Monotonic Is NP-complete....Pages 279-291 On the Semantics of Regular Expression Parsing in the Wild....Pages 292-304 Front Matter....Pages 305-305 Introducing Code Adviser: A DFA-driven Electronic Programming Tutor....Pages 307-312 Back Matter....Pages 313-316 ....Pages 317-317