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.
Author(s): Janusz Brzozowski (auth.), Adrian-Horia Dediu, Henning Fernau, Carlos Martín-Vide (eds.)
Series: Lecture Notes in Computer Science 6031 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 622
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Artificial Intelligence (incl. Robotics); Mathematical Logic and Formal Languages; Pattern Recognition; Logics and Meanings of Programs
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 -
