Language and Automata Theory and Applications: 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings

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 -