Ebook: Language and Automata Theory and Applications: 7th International Conference, LATA 2013, Bilbao, Spain, April 2-5, 2013. Proceedings

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 verification; 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 artificial 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.

---

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.

---

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.
Content:
Front Matter....Pages -
Complexity Dichotomy for Counting Problems....Pages 1-11
Algorithms for Analyzing and Verifying Infinite-State Recursive Probabilistic Systems....Pages 12-12
Recursion Schemes, Collapsible Pushdown Automata and Higher-Order Model Checking....Pages 13-41
Discrete Linear Dynamical Systems....Pages 42-42
XML Schema Management: A Challenge for Automata Theory....Pages 43-43
On the Complexity of Shortest Path Problems on Discounted Cost Graphs....Pages 44-55
Termination of Rule-Based Calculi for Uniform Semi-Unification....Pages 56-67
Deciding WQO for Factorial Languages....Pages 68-79
On the Construction of a Family of Automata That Are Generically Non-minimal....Pages 80-91
Limited Non-determinism Hierarchy of Counter Automata....Pages 92-103
Unambiguous Automata Denoting Finitely Sequential Functions....Pages 104-115
Duplication-Loss Genome Alignment: Complexity and Algorithm....Pages 116-127
Maximizing Entropy over Markov Processes....Pages 128-140
MAT Learning of Universal Automata....Pages 141-152
A Graph Polynomial Approach to Primitivity....Pages 153-164
Suffix Trees for Partial Words and the Longest Common Compatible Prefix Problem....Pages 165-176
Dynamic Communicating Automata and Branching High-Level MSCs....Pages 177-189
Visibly Pushdown Automata: Universality and Inclusion via Antichains....Pages 190-201
Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions....Pages 202-213
How to Travel between Languages....Pages 214-225
Execution Information Rate for Some Classes of Automata....Pages 226-237
Decidability and Complexity Results for Verification of Asynchronous Broadcast Networks....Pages 238-249
The Buffered ?-Calculus: A Model for Concurrent Languages....Pages 250-261
Mix-Automatic Sequences....Pages 262-274
A Multivariate Analysis of Some DFA Problems....Pages 275-286
On the Size Complexity of Deterministic Frequency Automata....Pages 287-298
On the Number of Unbordered Factors....Pages 299-310
Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences....Pages 311-322
Efficient Submatch Extraction for Practical Regular Expressions....Pages 323-334
Determinacy and Subsumption for Single-Valued Bottom-Up Tree Transducers....Pages 335-346
Revealing vs. Concealing: More Simulation Games for B?chi Inclusion....Pages 347-358
On Bounded Languages and Reversal-Bounded Automata....Pages 359-370
Rewrite Closure and CF Hedge Automata....Pages 371-382
Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing....Pages 383-394
From Regular Tree Expression to Position Tree Automaton....Pages 395-406
Convergence of Newton’s Method over Commutative Semirings....Pages 407-418
Counting Minimal Symmetric Difference NFAs....Pages 419-430
Interval Logics and ?B-Regular Languages....Pages 431-443
Eliminating Stack Symbols in Push-Down Automata and Linear Indexed Grammars....Pages 444-455
Asynchronous PC Systems of Pushdown Automata....Pages 456-467
Model Checking Metric Temporal Logic over Automata with One Counter....Pages 468-479
Coinductive Proof Techniques for Language Equivalence....Pages 480-492
Ostrowski Numeration and the Local Period of Sturmian Words....Pages 493-503
Boolean Algebras of Regular ?-Languages....Pages 504-515
Pumping, Shrinking and Pronouns: From Context Free to Indexed Grammars....Pages 516-522
Online Matching of Multiple Regular Patterns with Gaps and Character Classes....Pages 523-534
Infiniteness and Boundedness in 0L, DT0L, and T0L Systems....Pages 535-546
Uniformisation of Two-Way Transducers....Pages 547-558
A Conditional Superpolynomial Lower Bound for Extended Resolution....Pages 559-569
A Turing Machine Distance Hierarchy....Pages 570-578
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.
Content:
Front Matter....Pages -
Complexity Dichotomy for Counting Problems....Pages 1-11
Algorithms for Analyzing and Verifying Infinite-State Recursive Probabilistic Systems....Pages 12-12
Recursion Schemes, Collapsible Pushdown Automata and Higher-Order Model Checking....Pages 13-41
Discrete Linear Dynamical Systems....Pages 42-42
XML Schema Management: A Challenge for Automata Theory....Pages 43-43
On the Complexity of Shortest Path Problems on Discounted Cost Graphs....Pages 44-55
Termination of Rule-Based Calculi for Uniform Semi-Unification....Pages 56-67
Deciding WQO for Factorial Languages....Pages 68-79
On the Construction of a Family of Automata That Are Generically Non-minimal....Pages 80-91
Limited Non-determinism Hierarchy of Counter Automata....Pages 92-103
Unambiguous Automata Denoting Finitely Sequential Functions....Pages 104-115
Duplication-Loss Genome Alignment: Complexity and Algorithm....Pages 116-127
Maximizing Entropy over Markov Processes....Pages 128-140
MAT Learning of Universal Automata....Pages 141-152
A Graph Polynomial Approach to Primitivity....Pages 153-164
Suffix Trees for Partial Words and the Longest Common Compatible Prefix Problem....Pages 165-176
Dynamic Communicating Automata and Branching High-Level MSCs....Pages 177-189
Visibly Pushdown Automata: Universality and Inclusion via Antichains....Pages 190-201
Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions....Pages 202-213
How to Travel between Languages....Pages 214-225
Execution Information Rate for Some Classes of Automata....Pages 226-237
Decidability and Complexity Results for Verification of Asynchronous Broadcast Networks....Pages 238-249
The Buffered ?-Calculus: A Model for Concurrent Languages....Pages 250-261
Mix-Automatic Sequences....Pages 262-274
A Multivariate Analysis of Some DFA Problems....Pages 275-286
On the Size Complexity of Deterministic Frequency Automata....Pages 287-298
On the Number of Unbordered Factors....Pages 299-310
Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences....Pages 311-322
Efficient Submatch Extraction for Practical Regular Expressions....Pages 323-334
Determinacy and Subsumption for Single-Valued Bottom-Up Tree Transducers....Pages 335-346
Revealing vs. Concealing: More Simulation Games for B?chi Inclusion....Pages 347-358
On Bounded Languages and Reversal-Bounded Automata....Pages 359-370
Rewrite Closure and CF Hedge Automata....Pages 371-382
Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing....Pages 383-394
From Regular Tree Expression to Position Tree Automaton....Pages 395-406
Convergence of Newton’s Method over Commutative Semirings....Pages 407-418
Counting Minimal Symmetric Difference NFAs....Pages 419-430
Interval Logics and ?B-Regular Languages....Pages 431-443
Eliminating Stack Symbols in Push-Down Automata and Linear Indexed Grammars....Pages 444-455
Asynchronous PC Systems of Pushdown Automata....Pages 456-467
Model Checking Metric Temporal Logic over Automata with One Counter....Pages 468-479
Coinductive Proof Techniques for Language Equivalence....Pages 480-492
Ostrowski Numeration and the Local Period of Sturmian Words....Pages 493-503
Boolean Algebras of Regular ?-Languages....Pages 504-515
Pumping, Shrinking and Pronouns: From Context Free to Indexed Grammars....Pages 516-522
Online Matching of Multiple Regular Patterns with Gaps and Character Classes....Pages 523-534
Infiniteness and Boundedness in 0L, DT0L, and T0L Systems....Pages 535-546
Uniformisation of Two-Way Transducers....Pages 547-558
A Conditional Superpolynomial Lower Bound for Extended Resolution....Pages 559-569
A Turing Machine Distance Hierarchy....Pages 570-578
Back Matter....Pages -
....