The 45 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 116 submissions. The papers cover the following topics: algebraic language theory; algorithms on automata and words; automata and logic; automata for system analysis and program verification; automata, concurrency and Petri nets; automatic structures; combinatorics on words; computability; computational complexity; descriptional complexity; DNA and other models of bio-inspired computing; foundations of finite state technology; foundations of XML; grammars (Chomsky hierarchy, contextual, unification, categorial, etc.); grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; parsing; patterns; quantum, chemical and optical computing; semantics; string and combinatorial issues in computational biology and bioinformatics; string processing algorithms; symbolic dynamics; term rewriting; transducers; trees, tree languages and tree automata; weighted automata.
Table of Contents
A Brief History of Strahler Numbers.-On the Parikh Membership Problem for FAs, PDAs, and CMs.-Matchings, Random Walks, and Sampling.- Interprocedural Information Flow Analysis of XML Processors.-Computing Optimal Reachability Costs in Priced Dense-Timed Pushdown Automata.-Formulae for Polyominoes on Twisted Cylinders.-Picture Codes with Finite Deciphering Delay.-Networks of Polarized Evolutionary Processors Are Computationally Complete.-Two Double-Exponential Gaps for Automata with a Limited Pushdown.-Covering Pairs in Directed Acyclic Graphs.-Efficient List-Based Computation of the String Subsequence Kernel.-Channel Synthesis Revisited.-Characterisation of the State Spaces of Live and Bounded Marked Graph Petri Nets.-Computing Depths of Patterns.-Solving Equations on Words with Morphisms and Antimorphisms.-On the Arithmetics of Discrete Figures.-On the List Update Problem with Advice.-Shift-Reduce Parsers for Transition Networks.-Optimal Sorting Networks.-Satisfiability for MTL and TPTL over Non-monotonic Data Words.-(k,l)-Unambiguity and Quasi-Deterministic Structures: An Alternative for the Determinization.-Solutions to the Multi-dimensional Equal Powers Problem Constructed by Composition of Rectangular Morphisms.-Succinct Encodings of Graph Isomorphism.-Extremal Combinatorics of Reaction Systems.-Stochastic k-Tree Grammar and Its Application in Biomolecular Structure Modeling.-Weighted Automata and Logics for Infinite Nested Words.-Algebraic Tools for the Overlapping Tile Product.-Reachability Analysis with State-Compatible Automata.-Counting Models of Linear-Time Temporal Logic.-ω-rational Languages: High Complexity Classes vs. Borel Hierarchy.-On Context-Diverse Repeats and Their Incremental Computation.-Ordered Counter-Abstraction: Refinable Subword Relations for Parameterized Verification.-On SAT Representations of XOR Constraints.-Minimal Triangulation Algorithms for Perfect Phylogeny Problems.-On Computability and Learnability of the Pumping Lemma Function.-Interval Temporal Logic Semantics of Box Algebra.-Are Good-for-Games Automata Good for Probabilistic Model Checking.-Top-Down Tree Edit-Distance of Regular Tree Languages.-DFA with a Bounded Activity Level.-Learning Sequential Tree-to-Word Transducers.-Probabilistic Simulation for Probabilistic Data-Aware Business Processes.-Expressiveness of Dynamic Networks of Timed Petri Nets.-Distinguishing Pattern Languages with Membership Examples.-Extended Two-Way Ordered Restarting Automata for Picture Languages.-Weight-Reducing Hennie Machines and Their Descriptional Complexity.-Computing with Catalan Families.-Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata.-Probabilistic ω-Regular Expressions.-On the State Complexity of Semi-quantum Finite Automata.