Language and Automata Theory and Applications

This book constitutes the refereed proceedings of the 8th International Conference on Language and Automata Theory and Applications, LATA 2014, held in Madrid, Spain in March 2014.
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.

Inhalt

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.