Language and Automata Theory and Applications : 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012, Proceedings

This book constitutes the refereed proceedings of the 6th International Conference on Language and Automata Theory and Applications, LATA 2012, held in A Coruña, Spain in March 2012. The 41 revised full papers presented together with 3 invited talks and 2 invited tutorials were carefully reviewed and selected from 114 initial submissions. The volume features contributions from both classical theory fields and application areas; e.g. innformatics, systems biology, language technology, artificial intelligence, etc. Among the topics covered are algebraic language theory, automata and logic, systems analysis, systems verifications, computational complexity, decidability, unification, graph transformations, language-based cryptography, and applications in data mining, computational learning, and pattern recognition. Front Matter....Pages - Measuring Information in Timed Languages....Pages 1-2 Automata-Based Symbolic Representations of Polyhedra....Pages 3-20 Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory....Pages 21-37 A Parameterized Complexity Tutorial....Pages 38-56 The Computer Science of DNA Nanotechnology....Pages 57-57 The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems....Pages 58-69 Unification Modulo Chaining....Pages 70-82 Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits....Pages 83-94 Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space....Pages 95-105 Defining Contexts in Context-Free Grammars....Pages 106-118 Longest Common Extensions via Fingerprinting....Pages 119-130 Fast and Cache-Oblivious Dynamic Programming with Local Dependencies....Pages 131-142 An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings....Pages 143-154 Strong Termination for Gap-Order Constraint Abstractions of Counter Systems....Pages 155-168 Covering Space in the Besicovitch Topology....Pages 169-178 Approximate Regular Expressions and Their Derivatives....Pages 179-191 Catalytic Petri Nets Are Turing Complete....Pages 192-203 Computational Complexity of Rule Distributions of Non-uniform Cellular Automata....Pages 204-215 Conservative Groupoids Recognize Only Regular Languages....Pages 216-227 Advice Complexity of Online Coloring for Paths....Pages 228-239 A Faster Grammar-Based Self-index....Pages 240-251 Learnability of Co-r.e. Classes....Pages 252-263 Two-Way Automata Making Choices Only at the Endmarkers....Pages 264-276 Polynomial-Time Algorithms for Learning Typed Pattern Languages....Pages 277-288 Forbidding Sets and Normal Forms for Language Forbidding-Enforcing Systems....Pages 289-300 Applying Tree Languages in Proof Theory....Pages 301-312 The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints....Pages 313-324 Characterizing the Rational Functions by Restarting Transducers....Pages 325-336 Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines....Pages 337-350 Feasible Automata for Two-Variable Logic with Successor on Data Words....Pages 351-362 Nash Equilibria in Concurrent Priced Games....Pages 363-376 Computing by Observing Insertion....Pages 377-388 On the Parameterized Complexity of Default Logic and Autoepistemic Logic....Pages 389-400 Cayley Graph Automatic Groups Are Not Necessarily Cayley Graph Biautomatic....Pages 401-407 On Model Checking for Visibly Pushdown Automata....Pages 408-419 Automaton-Based Array Initialization Analysis....Pages 420-432 Dynamics of Circuits and Intersecting Circuits....Pages 433-444 Canonizable Partial Order Generators....Pages 445-457 Ogden’s Lemma for ET0L Languages....Pages 458-467 Patterns with Bounded Treewidth....Pages 468-479 P–NP Threshold for Synchronizing Road Coloring....Pages 480-489 k -Automatic Sets of Rational Numbers....Pages 490-501 On Stable and Unstable Limit Sets of Finite Families of Cellular Automata....Pages 502-513 Automaton Ranks of Some Self-similar Groups....Pages 514-525 One-Way Reversible and Quantum Finite Automata with Advice....Pages 526-537 Integration of the Dual Approaches in the Distributional Learning of Context-Free Grammars....Pages 538-550 Back Matter....Pages - 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.