Language and Automata Theory and Applications

1. Front Matter

   PDF

2. Invited Talks

   1. Measuring Information in Timed Languages

      • Eugene Asarin

      Pages 1-2

   2. Automata-Based Symbolic Representations of Polyhedra

      • Bernard Boigelot, Julien Brusten, Jean-François Degbomont

      Pages 3-20

   3. Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory

      • Gilles Dowek

      Pages 21-37

   4. A Parameterized Complexity Tutorial

      • Rod Downey

      Pages 38-56

   5. The Computer Science of DNA Nanotechnology

      • Jack H. Lutz

      Pages 57-57

3. Regular Papers

   1. The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems

      • Parosh Aziz Abdulla, Mohamed Faouzi Atig, Jari Stenman

      Pages 58-69

   2. Unification Modulo Chaining

      • Siva Anantharaman, Christopher Bouchard, Paliath Narendran, Michael Rusinowitch

      Pages 70-82

   3. Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits

      • Vikraman Arvind, Yadu Vasudev

      Pages 83-94

   4. Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space

      • Holger Bock Axelsen

      Pages 95-105

   5. Defining Contexts in Context-Free Grammars

      • Mikhail Barash, Alexander Okhotin

      Pages 106-118

   6. Longest Common Extensions via Fingerprinting

      • Philip Bille, Inge Li Gørtz, Jesper Kristensen

      Pages 119-130

   7. Fast and Cache-Oblivious Dynamic Programming with Local Dependencies

      • Philip Bille, Morten Stöckel

      Pages 131-142

   8. An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings

      • Beate Bollig, Tobias Pröger

      Pages 143-154

   9. Strong Termination for Gap-Order Constraint Abstractions of Counter Systems

      • Laura Bozzelli

      Pages 155-168

   10. Covering Space in the Besicovitch Topology

       • Julien Cervelle

       Pages 169-178

   11. Approximate Regular Expressions and Their Derivatives

       • Jean-Marc Champarnaud, Hadrien Jeanne, Ludovic Mignot

       Pages 179-191

   12. Catalytic Petri Nets Are Turing Complete

       • Gabriel Ciobanu, G. Michele Pinna

       Pages 192-203

   13. Computational Complexity of Rule Distributions of Non-uniform Cellular Automata

       • Alberto Dennunzio, Enrico Formenti, Julien Provillard

       Pages 204-215

   14. Conservative Groupoids Recognize Only Regular Languages

       • Danny Dubé, Mario Latendresse, Pascal Tesson

       Pages 216-227

This book constitutes the refereed proceedings of the 6th International Conference on Language and Automata Theory and Applications, LATA 2012, held in A Coruña, Spain in March 2012. The 41 revised full papers presented together with 3 invited talks and 2 invited tutorials were carefully reviewed and selected from 114 initial submissions. The volume features contributions from both classical theory fields and application areas; e.g. innformatics, systems biology, language technology, artificial intelligence, etc. Among the topics covered are algebraic language theory, automata and logic, systems analysis, systems verifications, computational complexity, decidability, unification, graph transformations, language-based cryptography, and applications in data mining, computational learning, and pattern recognition.

• dynamical systems
• formal languages
• model checking
• numerical constraints
• regular expressions
• algorithm analysis and problem complexity

• Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain

  Adrian-Horia Dediu, Carlos Martín-Vide

Policies and ethics