Language and Automata Theory and Applications: 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010, Proceedings (Lecture Notes in Computer Science, 6031)

This book constitutes the proceedings of the 4th International Conference, LATA 2010, held in May 2010 in Trier, Germany. The 47 full papers presented were carefully selected from 115 submissions and focus on topics such as algebraic language theory , algorithmic learning, bioinformatics, computational biology, pattern recognition, program verification, term rewriting and tree machines. Front Matter....Pages - Complexity in Convex Languages....Pages 1-15 Three Learnable Models for the Description of Language....Pages 16-31 Arbology: Trees and Pushdown Automata....Pages 32-49 Analysis of Communicating Automata....Pages 50-57 Complexity of the Satisfiability Problem for a Class of Propositional Schemata....Pages 58-69 A Simple n -Dimensional Intrinsically Universal Quantum Cellular Automaton....Pages 70-81 A Fast Longest Common Subsequence Algorithm for Similar Strings....Pages 82-93 Abelian Square-Free Partial Words....Pages 94-105 Avoidable Binary Patterns in Partial Words....Pages 106-117 Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata....Pages 118-129 Pregroup Grammars with Letter Promotions....Pages 130-141 A Hierarchical Classification of First-Order Recurrent Neural Networks....Pages 142-153 Choosing Word Occurrences for the Smallest Grammar Problem....Pages 154-165 Agreement and Cliticization in Italian: A Pregroup Analysis....Pages 166-177 Geometricity of Binary Regular Languages....Pages 178-189 On the Expressive Power of FO[ + ]....Pages 190-201 Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach....Pages 202-213 Operator Precedence and the Visibly Pushdown Property....Pages 214-226 On the Maximal Number of Cubic Runs in a String....Pages 227-238 On the Hamiltonian Operators for Adiabatic Quantum Reduction of SAT....Pages 239-248 Parametric Metric Interval Temporal Logic....Pages 249-260 Short Witnesses and Accepting Lassos in ω -Automata....Pages 261-272 Grammar-Based Compression in a Streaming Model....Pages 273-284 Simplifying Regular Expressions....Pages 285-296 A Programming Language Tailored to the Specification and Solution of Differential Equations Describing Processes on Networks....Pages 297-308 The Inclusion Problem for Regular Expressions....Pages 309-320 Learnability of Automatic Classes....Pages 321-332 Untestable Properties Expressible with Four First-Order Quantifiers....Pages 333-343 The Copying Power of Well-Nested Multiple Context-Free Grammars....Pages 344-355 Post Correspondence Problem with Partially Commutative Alphabets....Pages 356-367 Reversible Pushdown Automata....Pages 368-379 String Extension Learning Using Lattices....Pages 380-391 The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape....Pages 392-402 Primitive Words Are Unavoidable for Context-Free Languages....Pages 403-413 Modal Nonassociative Lambek Calculus with Assumptions: Complexity and Context-Freeness....Pages 414-425 Hard Counting Problems for Partial Words....Pages 426-438 Exact Analysis of Horspool’s and Sunday’s Pattern Matching Algorithms with Probabilistic Arithmetic Automata....Pages 439-450 SA-REPC – Sequence Alignment with Regular Expression Path Constraint....Pages 451-462 CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages....Pages 463-474 A Boundary between Universality and Non-universality in Extended Spiking Neural P Systems....Pages 475-487 Using Sums-of-Products for Non-standard Reasoning....Pages 488-499 Restarting Automata with Structured Output and Functional Generative Description....Pages 500-511 A Randomized Numerical Aligner (rNA)....Pages 512-523 Language-Based Comparison of Petri Nets with Black Tokens, Pure Names and Ordered Data....Pages 524-535 Verifying Complex Continuous Real-Time Systems with Coinductive CLP(R)....Pages 536-548 Incremental Building in Peptide Computing to Solve Hamiltonian Path Problem....Pages 549-560 Variable Automata over Infinite Alphabets....Pages 561-572 Some Minimality Results on Biresidual and Biseparable Automata....Pages 573-584 Extending Stochastic Context-Free Grammars for an Application in Bioinformatics....Pages 585-595 Chomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages....Pages 596-607 Complexity of Guided Insertion-Deletion in RNA-Editing....Pages 608-619 Back Matter....Pages - These proceedings containall the papers that werepresented at the 4th Inter- tional Conference on Language and Automata Theory and Applications (LATA 2010), held in Trier, Germany, during May 24-28, 2010. The scope of LATA is rather broad, including: algebraic language theory; algorithms on automata and words; automata and logic; automata for system analysis and program veri?cation; automata, concurrency and Petri nets; cel- lar automata; combinatorics on words; computability; computational compl- ity; computer 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 ?nite state te- nology; fuzzy and rough languages; grammars (Chomsky hierarchy, contextual, multidimensional, uni?cation, categorial, etc. ); grammars and automata arc- tectures; grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; language-based cryptog- phy; language-theoretic foundations of arti?cial intelligence and arti?cial life; neuralnetworks;parallelandregulatedrewriting;parsing;patternmatching and pattern recognition; patterns and codes; power series; quantum, chemical and optical computing; semantics; string and combinatorial issues in computational biology and bioinformatics; symbolic dynamics; term rewriting; text algorithms; textretrieval;transducers;trees,treelanguagesandtreemachines;andweighted machines. LATA 2010 received 115 submissions, many among them of good quality. Each one was reviewed by at least three Program Committee members plus, in mostcases,byadditionalexternalreferees. Afterathoroughandvividdiscussion phase, the committee decided to accept 47 papers (which means an acceptance rate of 40. 86%). The conference program also included four invited talks These proceedings containall the papers that werepresented at the 4th Inter- tional Conference on Language and Automata Theory and Applications (LATA 2010), held in Trier, Germany, during May 24-28, 2010. The scope of LATA is rather broad, including: algebraic language theory; algorithms on automata and words; automata and logic; automata for system analysis and program veri?cation; automata, concurrency and Petri nets; cel- lar automata; combinatorics on words; computability; computational compl- ity; computer 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?nite state te- nology; fuzzy and rough languages; grammars (Chomsky hierarchy, contextual, multidimensional, uni?cation, categorial, etc.); grammars and automata arc- tectures; grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; language-based cryptog- phy; language-theoretic foundations of arti?cial intelligence and arti?cial life; neuralnetworks;parallelandregulatedrewriting;parsing;patternmatching and pattern recognition; patterns and codes; power series; quantum, chemical and optical computing; semantics; string and combinatorial issues in computational biology and bioinformatics; symbolic dynamics; term rewriting; text algorithms; textretrieval;transducers;trees, treelanguagesandtreemachines;andweighted machines. LATA 2010 received 115 submissions, many among them of good quality. Each one was reviewed by at least three Program Committee members plus, in mostcases, byadditionalexternalreferees. Afterathoroughandvividdiscussion phase, the committee decided to accept 47 papers (which means an acceptance rate of 40. 86%). The conference program also included four invited talks 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. trees, tree languages and tree automata;