Language and Automata Theory and Applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings (Lecture Notes in Computer Science Book 9618)

This book constitutes the refereed proceedings of the 10th International Conference on Language and Automata Theory and Applications, LATA 2016, held in Prague, Czech Republic, in March 2016. The 42 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 119 submissions. The papers cover the following topics: algebraic language theory; algorithms for semi-structured data mining, algorithms on automata and words; automata and logic; automata for system analysis and program verification; automata networks, concurrency and Petri nets; automatic structures; cellular automata, codes, combinatorics on words; computational complexity; data and image compression; descriptional complexity; digital libraries and document engineering; foundations of finite state technology; foundations of XML; fuzzy and rough languages; grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; parallel and regulated rewriting; parsing; patterns; 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. Front Matter....Pages I-XXII Front Matter....Pages 1-1 Non-Zero Sum Games for Reactive Synthesis....Pages 3-23 Tangles and Connectivity in Graphs....Pages 24-41 Restricted Turing Machines and Language Recognition....Pages 42-56 Automata for Ontologies....Pages 57-60 Front Matter....Pages 61-61 A Logical Characterization for Dense-Time Visibly Pushdown Automata....Pages 63-75 A Complexity Measure on Büchi Automata....Pages 76-88 Compositional Bisimulation Minimization for Interval Markov Decision Processes....Pages 89-101 A Weighted MSO Logic with Storage Behaviour and Its Büchi-Elgot-Trakhtenbrot Theorem....Pages 102-113 Front Matter....Pages 114-126 Colored Nested Words....Pages 127-139 Input-Driven Queue Automata with Internal Transductions....Pages 141-141 Periodic Generalized Automata over the Reals....Pages 143-155 Minimal Separating Sequences for All Pairs of States....Pages 156-167 Forkable Regular Expressions....Pages 168-180 On the Levenshtein Automaton and the Size of the Neighbourhood of a Word....Pages 181-193 Front Matter....Pages 194-206 Parallelogram Morphisms and Circular Codes....Pages 207-218 On Del-Robust Primitive Partial Words with One Hole....Pages 219-219 Front Matter....Pages 221-232 On XOR Lemma for Polynomial Threshold Weight and Length....Pages 233-244 Front Matter....Pages 245-255 The Beachcombers’ Problem: Walking and Searching from an Inner Point of a Line....Pages 257-257 Using Duality in Circuit Complexity....Pages 259-269 The Minimum Entropy Submodular Set Cover Problem....Pages 257-257 On the Capacity of Capacitated Automata....Pages 270-282 On Limited Nondeterminism and ACC Circuit Lower Bounds....Pages 283-294 The Complexity of Induced Tree Reconfiguration Problems....Pages 295-306 Front Matter....Pages 307-319 The Missing Case in Chomsky-Schützenberger Theorem....Pages 320-329 Homomorphic Characterizations of Indexed Languages....Pages 330-342 Ogden’s Lemma, Multiple Context-Free Grammars, and the Control Language Hierarchy....Pages 343-343 Front Matter....Pages 345-358 Steganography Based on Pattern Languages....Pages 359-370 Inferring a Relax NG Schema from XML Documents....Pages 371-383 Noise Free Multi-armed Bandit Game....Pages 385-385 Front Matter....Pages 387-399 Properties of Regular DAG Languages....Pages 400-411 Normal Form on Linear Tree-to-Word Transducers....Pages 412-423 A Kleene Theorem for Weighted Tree Automata over Tree Valuation Monoids....Pages 425-425 Hankel Matrices for Weighted Visibly Pushdown Automata....Pages 427-438 Linear Context-Free Tree Languages and Inverse Homomorphisms....Pages 439-451 Front Matter....Pages 452-463 Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages....Pages 464-477 The Word Problem for HNN-extensions of Free Inverse Semigroups....Pages 478-489 Front Matter....Pages 491-491 Between a Rock and a Hard Place – Uniform Parsing for Hyperedge Replacement DAG Grammars....Pages 493-505 Front Matter....Pages 506-517 An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time....Pages 519-519 Front Matter....Pages 521-532 Accurate Approximate Diagnosability of Stochastic Systems....Pages 519-519 Proof–Based Synthesis of Sorting Algorithms for Trees....Pages 533-546 Front Matter....Pages 547-547 Reversible Shrinking Two-Pushdown Automata....Pages 549-561 Reachability in Resource-Bounded Reaction Systems....Pages 562-575 Canonical Multi-target Toffoli Circuits....Pages 577-577 Back Matter....Pages 579-591 ....Pages 592-602 This book constitutes the refereed proceedings of the 7th International Conference on Language and Automata Theory and Applications, LATA 2013, held in Bilbao, Spain in April 2013. The 45 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 97 initial submissions. The volume features contributions from both classical theory fields and application areas (bioinformatics, systems biology, language technology, artificial intelligence, etc.). Among the topics covered are algebraic language theory; algorithms for semi-structured data mining; algorithms on automata and words; automata and logic; automata for system analysis and program verifiation; automata, concurrency and Petri nets; automatic structures; cellular automata; combinatorics on words; computability; computational complexity; computational linguistics; data and image compression; decidability questions on words and languages; descriptional complexity; DNA and other models of bio-inspired computing; document engineering; foundations of finite state technology; foundations of XML; fuzzy and rough languages; grammars (Chomsky hierarchy, contextual, multidimensional, unification, categorial, etc.); grammars and automata architectures; grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; language-based cryptography; language-theoretic foundations of artificial intelligence and artifi- cial life; parallel and regulated rewriting; parsing; pattern recognition; patterns and codes; power series; quantum, chemical and optical computing; semantics; string and combinatorial issues in computational biology and bioinformatics; string processing algorithms; symbolic dynamics; symbolic neural networks; term rewriting; transducers; trees, tree languages and tree automata; weighted automata.