Implementation And Application Of Automata: 14th International Conference, Ciaa 2009, Sydney, Australia, July 14-17, 2009, Proceedings (lecture Notes In Computer Science)

This book constitutes the thoroughly refereed papers of the 14th International Conference on Implementation and Application of Automata, CIAA 2009, held in Sydney, Austrialia, in July 2009. The 23 revised full papers togehter with 6 short papers were carefully selected from 42 submissions. The papers cover various topics in the theory, implementation, and applications of automata and related structures. Front Matter....Pages - Implementation and Application of Automata in String Processing....Pages 1-1 Applications of Automata in XML Processing....Pages 2-2 Program Analysis through Finite Tree Automata....Pages 3-3 An n log n Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton....Pages 4-13 On Extremal Cases of Hopcroft’s Algorithm....Pages 14-23 Compact Normal Form for Regular Languages as Xor Automata....Pages 24-33 Cellular Automata with Sparse Communication....Pages 34-43 A Cellular Automaton Model for Car Traffic with a Slow-to-Stop Rule....Pages 44-53 On Parallel Implementations of Deterministic Finite Automata....Pages 54-64 FAdo and GUItar....Pages 65-74 A Testing Framework for Finite-State Morphology....Pages 75-83 A Table Compression Method for Extended Aho-Corasick Automaton....Pages 84-93 Compact Representation for Answer Sets of n -ary Regular Queries....Pages 94-104 Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata....Pages 105-114 Random Generation of Deterministic Tree (Walking) Automata....Pages 115-124 Hedge Pattern Partial Derivative....Pages 125-134 TAGED Approximations for Temporal Properties Model-Checking....Pages 135-144 Verifying Parallel Programs with Dynamic Communication Structures....Pages 145-154 Fixpoint Guided Abstraction Refinement for Alternating Automata....Pages 155-164 Automata-Based Termination Proofs....Pages 165-177 Implementation of State Elimination Using Heuristics....Pages 178-187 Short Regular Expressions from Finite Automata: Empirical Results....Pages 188-197 Small Extended Expressions for Acyclic Automata....Pages 198-207 Quantum Queries on Permutations with a Promise....Pages 208-216 Time-Optimal Winning Strategies for Poset Games....Pages 217-226 Amount of Nonconstructivity in Finite Automata....Pages 227-236 Multiflex: A Multilingual Finite-State Tool for Multi-Word Units....Pages 237-240 Efficient Parsing Using Filtered-Popping Recursive Transition Networks....Pages 241-244 Forest FIRE: A Taxonomy-based Toolkit of Tree Automata and Regular Tree Algorithms....Pages 245-248 Formally Synthesising a Protocol Converter: A Case Study....Pages 249-252 Compiler Generator Based on Restarting Automata....Pages 253-257 Are Statecharts Finite Automata?....Pages 258-261 Back Matter....Pages - Annotation This book constitutes the thoroughly refereed papers of the 14th International Conference on Implementation and Application of Automata, CIAA 2009, held in Sydney, Austrialia, in July 2009. The 23 revised full papers together with 6 short papers were carefully selected from 42 submissions. The papers cover various topics in the theory, implementation, and applications of automata and related structures