Markus Holzer, Martin Kutrib (auth.), Oscar H. Ibarra, Bala Ravikumar (eds.)354070843X, 9783540708438
This book constitutes the thoroughly refereed post-proceedings of the 13th International Conference on Implementation and Application of Automata, CIAA 2008, held in San Francisco, USA, in July 2008.
The 26 revised full papers togehter with 4 invited papers were carefully reviewed and selected from 40 submissions and have gone through two rounds of reviewing and improvement. The papers cover various topics in the theory, implementation, and applications of automata and related structures.
Table of contents :
Front Matter….Pages –
Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity….Pages 1-16
Language Decompositions, Primality, and Trajectory-Based Operations….Pages 17-22
Automata, Probability, and Recursion….Pages 23-32
Concurrency, Synchronization, and Conflicts in Petri Nets….Pages 33-35
Automated Compositional Reasoning of Intuitionistically Closed Regular Properties….Pages 36-45
Antimirov and Mosses’s Rewrite System Revisited….Pages 46-56
Antichain-Based Universality and Inclusion Testing over Nondeterministic Finite Tree Automata….Pages 57-67
Testing Whether a Binary and Prolongeable Regular Language L Is Geometrical or Not on the Minimal Deterministic Automaton of Pref ( L )….Pages 68-77
Hopcroft’s Minimization Technique: Queues or Stacks?….Pages 78-91
Learning Regular Languages Using Nondeterministic Finite Automata….Pages 92-101
Multi-Return Macro Tree Transducers….Pages 102-111
Computing Convex Hulls by Automata Iteration….Pages 112-121
A Translation from the HTML DTD into a Regular Hedge Grammar….Pages 122-131
Tree-Series-to-Tree-Series Transformations….Pages 132-140
Automata-Theoretic Analysis of Bit-Split Languages for Packet Scanning….Pages 141-150
Pattern Matching in DCA Coded Text….Pages 151-160
Five Determinisation Algorithms….Pages 161-170
Persistent Computations of Turing Machines….Pages 171-180
On Complexity of Two Dimensional Languages Generated by Transducers….Pages 181-190
Games for Temporal Logics on Trees….Pages 191-200
A Run-Time Efficient Implementation of Compressed Pattern Matching Automata….Pages 201-211
Composed Bisimulation for Tree Automata….Pages 212-222
Hyper-Minimization in O ( n 2 )….Pages 223-231
Deterministic Pushdown Automata and Unary Languages….Pages 232-241
Finite Eilenberg Machines….Pages 242-251
The Number of Runs in Sturmian Words….Pages 252-261
3-Way Composition of Weighted Finite-State Transducers….Pages 262-273
Progressive Solutions to FSM Equations….Pages 274-282
Combination of Context-Free Grammars and Tree Automata for Unranked and Ranked Trees….Pages 283-285
Approximate Periods with Levenshtein Distance….Pages 286-287
Back Matter….Pages –
Reviews
There are no reviews yet.