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.
Author(s): Gonzalo Navarro (auth.), Sebastian Maneth (eds.)
Series: Lecture Notes in Computer Science 5642 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 263
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; System Performance and Evaluation; Software Engineering
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 -
