Language and Automata Theory and Applications

1. Front Matter

   Pages I-XIV

   PDF

2. Invited Talks

   1. A Brief History of Strahler Numbers

      • Javier Esparza, Michael Luttenberger, Maximilian Schlund

      Pages 1-13

   2. On the Parikh Membership Problem for FAs, PDAs, and CMs

      • Oscar H. Ibarra, Bala Ravikumar

      Pages 14-31

   3. Matchings, Random Walks, and Sampling

      • Sanjeev Khanna

      Pages 32-33

   4. Interprocedural Information Flow Analysis of XML Processors

      • Helmut Seidl, Máté Kovács

      Pages 34-61

3. Regular Papers

   1. Computing Optimal Reachability Costs in Priced Dense-Timed Pushdown Automata

      • Parosh Aziz Abdulla, Mohamed Faouzi Atig, Jari Stenman

      Pages 62-75

   2. Formulae for Polyominoes on Twisted Cylinders

      • Gadi Aleksandrowicz, Andrei Asinowski, Gill Barequet, Ronnie Barequet

      Pages 76-87

   3. Picture Codes with Finite Deciphering Delay

      • Marcella Anselmo, Dora Giammarresi, Maria Madonia

      Pages 88-100

   4. Networks of Polarized Evolutionary Processors Are Computationally Complete

      • Fernando Arroyo, Sandra Gómez Canaval, Victor Mitrana, Ştefan Popescu

      Pages 101-112

   5. Two Double-Exponential Gaps for Automata with a Limited Pushdown

      • Zuzana Bednárová, Viliam Geffert

      Pages 113-125

   6. Covering Pairs in Directed Acyclic Graphs

      • Niko Beerenwinkel, Stefano Beretta, Paola Bonizzoni, Riccardo Dondi, Yuri Pirola

      Pages 126-137

   7. Efficient List-Based Computation of the String Subsequence Kernel

      • Slimane Bellaouar, Hadda Cherroun, Djelloul Ziadi

      Pages 138-148

   8. Channel Synthesis Revisited

      • Béatrice Bérard, Olivier Carton

      Pages 149-160

   9. Characterisation of the State Spaces of Live and Bounded Marked Graph Petri Nets

      • Eike Best, Raymond Devillers

      Pages 161-172

   10. Computing Depths of Patterns

       • Francine Blanchet-Sadri, Andrew Lohr, Sean Simmons, Brent Woodhouse

       Pages 173-185

   11. Solving Equations on Words with Morphisms and Antimorphisms

       • Alexandre Blondin Massé, Sébastien Gaboury, Sylvain Hallé, Michaël Larouche

       Pages 186-197

   12. On the Arithmetics of Discrete Figures

       • Alexandre Blondin Massé, Amadou Makhtar Tall, Hugo Tremblay

       Pages 198-209

   13. On the List Update Problem with Advice

       • Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz

       Pages 210-221

   14. Shift-Reduce Parsers for Transition Networks

       • Luca Breveglieri, Stefano Crespi Reghizzi, Angelo Morzenti

       Pages 222-235

   15. Optimal Sorting Networks

       • Daniel Bundala, Jakub Závodný

       Pages 236-247

This book constitutes the refereed proceedings of the 8th International Conference on Language and Automata Theory and Applications, LATA 2014, held in Madrid, Spain in March 2014.
The 45 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 116 submissions. The papers cover the following topics: algebraic language theory; algorithms on automata and words; automata and logic; automata for system analysis and program verification; automata, concurrency and Petri nets; automatic structures; combinatorics on words; computability; computational complexity; descriptional complexity; DNA and other models of bio-inspired computing; foundations of finite state technology; foundations of XML; grammars (Chomsky hierarchy, contextual, unification, categorial, etc.); grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; parsing; patterns; quantum, chemical and optical computing; semantics; string and combinatorial issues in computational biology and bioinformatics; string processing algorithms; symbolic dynamics; term rewriting; transducers; trees, tree languages and tree automata; weighted automata.

• algebraic complexity theory
• algebraic language theory
• combinatorics on words
• computational complexity
• concurrency
• data structures design and analysis
• formal languages and automata theory
• grammars and context-free languages
• graph algorithms
• logic
• parsers
• rewrite systems
• symbolic and algebraic algorithms
• symbolic and algebraic manipulation
• tree languages
• algorithm analysis and problem complexity

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

  Adrian-Horia Dediu, Carlos Martín-Vide

• School of Computer Science, Department of Software Engineering and Artificial Intelligence, Complutense University of Madrid, Madrid, Spain

  José-Luis Sierra-Rodríguez

• Fakultät für Informatik, Institut für Wissens- und Sprachverarbeitung, Otto-von-Guericke-Universität Magdeburg, Magdeburg, Germany

  Bianca Truthe

Policies and ethics