24-28 May 2010
Trier, Germany
4th INTERNATIONAL CONFERENCE ON LANGUAGE AND AUTOMATA THEORY AND APPLICATIO NS (LATA 2010) Trier, Germany, May 24-28, 2010 ******************************************************* Early registration deadline: February 15, 2010 !!! Please visit: http://grammars.grlmc.com/LATA2010/ ******************************************************* INVITED LECTURES John Brzozowski Complexity in Convex Languages Alexander Clark Three Learnable Models for the Description of Language Lauri Karttunen to be announced (tutorial) Borivoj Melichar Arbology: Trees and Pushdown Automata Anca Muscholl Analysis of Communicating Automata (tutorial) CONTRIBUTED PAPERS Vincent Aravantinos, Ricardo Caferra, and Nicolas Peltier Complexity of the Satisfiability Problem for a Class of Propositional Schem ata Pablo Arrighi and Jonathan Grattage A Simple n-dimensional Intrinsically Universal Quantum Cellular Automata Abdullah N. Arslan A Fast Longest Common Subsequence Algorithm for Similar Strings Francine Blanchet-Sadri, Jane Kim, Robert Mercas, William Severa, and Sean Simmons Abelian Square-Free Partial Words Francine Blanchet-Sadri, Robert Mercas, Sean Simmons, and Eric Weissenstein Avoidable Binary Patterns in Partial Words Nicolas Bousquet and Christof Loeding Equivalence and Inclusion Problem for Strongly Unambiguous Bchi Automata Wojciech Buszkowski and Lin Zhe Pregroup Grammars with Letter Promotions Jrmie Cabessa and Alessandro Villa A Hierarchical Classification of First-Order Recurrent Neural Networks Rafael Carrascosa, Franois Coste, Matthias Gall, and Gabriel Infante- Lpez Choosing Word Occurrences for the Smallest Grammar Problem Claudia Casadio Agreement and Cliticization in Italian: a Pregroup Analysis Jean-Marc Champarnaud, Jean-Philippe Dubernard, and Hadrien Jeanne Geometricity of Binary Regular Languages Christian Choffrut, Andreas Malcher, Carlo Mereghetti, and Beatrice Palano On the Expressive Power of FO[+] Christophe Costa Florencio and Henning Fernau Finding Consistent Categorial Grammars of Bounded Value: a Parameterized Ap proach Stefano Crespi Reghizzi and Dino Mandrioli Operator Precedence and the Visibly Pushdown Property Maxime Crochemore, Costas Iliopoulos, Marcin Kubica, Jakub Radoszewski, Woj ciech Rytter, and Tomasz Walen On the Maximal Number of Cubic Runs in a String William de la Cruz de los Santos and Guillermo Morales Luna On the Hamiltonian Operators for Adiabatic Quantum Reduction of SAT Barbara Di Giampaolo, Salvatore La Torre, and Margherita Napoli Parametric Metric Interval Temporal Logic Rdiger Ehlers Short Witnesses and Accepting Lassos in omega-automata Travis Gagie and Pawel Gawrychowski Grammar-Based Compression in a Streaming Model Hermann Gruber and Stefan Gulan Simplifying Regular Expressions. A Quantitative Perspective Reinhard Hemmerling, Katarina Smolenova, and Winfried Kurth A Programming Language Tailored to the Specification and Solution of Differ ential Equations Describing Processes on Networks Dag Hovland The Inclusion Problem for Regular Expressions Sanjay Jain, Qinglong Luo, and Frank Stephan Learnability of Automatic Classes Charles Jordan and Thomas Zeugmann Untestable First-Order Sentences: Four Universal and One Existential Quanti fier Makoto Kanazawa and Sylvain Salvati The Copying Power of Well-nested Multiple Context-free Grammars Barbara Klunder and Wojciech Rytter Post Correspondence Problem with Partially Commutative Alphabets Timo Ktzing and Anna Kasprzik String Extension Learning using Lattices Martin Kutrib and Andreas Malcher Reversible Pushdown Automata Alexander Letichevsky, Arsen Shoukourian, and Samvel Shoukourian The Equivalence Problem of Deterministic Multitape Finite Automata. A New P roof of Solvability Using A Multidimensional Tape Peter Leupold Primitive Words Are Unavoidable for Context-Free Languages Florin Manea and Catalin Tiseanu Hard Counting Problems for Partial Words Tobias Marschall and Sven Rahmann Exact Analysis of Horspool's and Sunday's Pattern Matching Algorithms with Probabilistic Arithmetic Automata Nimrod Milo, Tamar Pinhas, and Michal Ziv-Ukelson SAPC - Sequence Alignment with Path Constraints Sakthi Muthiah and Parameswaran Seshan Incremental Building in Peptide Computing to Solve Hamiltonian Path Problem Benedek Nagy and Friedrich Otto CD-Systems of Stateless Deterministic R(1)-Automata Accept all Rational Tra ce Languages Turlough Neary A Boundary Between Universality and Non-universality in Extended Spiking Ne ural P Systems Rafael Pealoza Using Sums-of-products for Non-standard Reasoning Martin Platek, Frantisek Mraz, and Marketa Lopatkova Restarting Automata with Structured Output and Functional Generative Descri ption Alberto Policriti, Alexandru I. Tomescu, and Francesco Vezzi A Randomized Numerical Aligner (rNA) Fernando Rosa-Velardo and Giorgio Delzanno A Language-based Comparison of Nets with Black Tokens, Pure Names and Order ed Data Neda Saeedloei and Gopal Gupta Verifying Complex Continuous Real-Time Systems with Coinductive CLP(R) Sarai Sheinvald, Orna Grumberg, and Orna Kupferman Variable Automata over Infinite Alphabets Hellis Tamm Some Minimality Results on BiRFSA and Biseparable Automata Frank Weinberg and Markus Nebel Extending Stochastic Context-Free Grammars for an Application in Bioinforma tics Ryo Yoshinaka, Yuichi Kaji, and Hiroyuki Seki Chomsky-Schtzenberger-Type Characterization of Multiple Context-Free Lan guages Hans Zantema Complexity of Guided Insertion-Deletion in RNA-editing Lin Zhe Modal Nonassociative Lambek Calculus with Assumptions: Complexity and Conte xt-freeness