The history of LATA starts in 2007. After three consecutive editions organized in Tarragona, the 4th edition (LATA 2010) took place in Trier, Germany while the 5th edition was back in Tarragona. Now it is the time for a new place to host LATA 2012, this time we go to A Coruña, Galicia, Spain.

Table of contents

Contact information

LATA 2012
Research Group on Mathematical Linguistics
Rovira i Virgili University
Av. Catalunya, 35
43002 Tarragona, Spain
Phone: +34-977-559543
Fax: +34-977-558386
e-Mail: florentinalilica.voicu (at)

LATA 2011 Picture

Click on the picture to see the complete page with pictures from LATA 2011 This is the group picture taken Friday, May 27, 2011.

2012 the Alan Turing Year (ATY)


A centenary celebration of the life and work of Alan Turing. The tutorial sessions Around the Physical Church-Turing Thesis presented by Gilles Dowek on March 6 and 7 are dedicated to this event.


The volume of proceedings published by Springer in the series of Lecture Notes in Computer Science ( LNCS volume 7183) will be available by the time of the conference.

Springer LNCS

Important dates

Event announced: July 16, 2011
Paper submission: October 12, 2011 (23:59h, CET)
Notification of paper acceptance or rejection: November 21, 2011
Final version of the paper for the LNCS proceedings: November 28, 2011
Early registration: December 5, 2011
Late registration: February 24, 2012
Starting of the conference: March 5, 2012
Submission to the post-conference special issue: June 22, 2012

LATA links

Links of interest

The following events are taking place in Tarragona. TPNC2012, October 1-5, 2012, WSMBio2012, February 20-24, 2012, WSLST2012, January 23-27, 2012, FSFLA2011, October 31 - November 4, 2011 .

Quality check

Our web pages are interoperable. This document validates as XHTML 1.0 Strict and CSS level 2.1.
Valid XHTML 1.0 Strict Valid CSS!

Program and slides

A pdf version of the program available as a banner (8.5M).
The available slides are accessible clicking on the titles of the papers.

Monday, March 5
15:00 - 16:00 Registration
16:00 - 16:10 Opening
16:10 - 17:10 Jack H. Lutz Bernard Boigelot: Automata-based Symbolic Representations of Polyhedra - Invited Talk
17:10 - 17:40 Coffee Break
17:40 - 18:30 Alexander Okhotin Eric Rowland and Jeffrey Shallit: k-Automatic Sets of Rational Numbers
Daniela Genova: Forbidding Sets and Normal Forms for Language Forbidding-Enforcing Systems

Tuesday, March 6
ATY 8:30 - 10:00 Enrico Formenti Gilles Dowek: Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory (I) - Invited Tutorial
10:00 - 10:15 Break
10:15 - 11:55 Bernard Boigelot Oscar H. Ibarra and Nicholas Q. Tran: Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines
Tang Van Nguyen and Hitoshi Ohsaki: On Model Checking for Visibly Pushdown Automata
Parosh Aziz Abdulla, Mohamed Faouzi Atig, and Jari Stenman: The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems
Alexander Krassovitskiy and Peter Leupold: Computing by Observing Insertion
11:55 - 12:25 Coffee Break
12:25 - 14:05 Amparo
Alexei Miasnikov and Zoran Šunić: Cayley Graph Automatic Groups are not necessarily Cayley Graph Biautomatic
Julien Cervelle: Covering Space in the Besicovitch Topology
Danny Dubé, Mario Latendresse, and Pascal Tesson: Conservative Groupoids Recognize only Regular Languages
Stefan Hetzl: Applying Tree Languages in Proof Theory
14:05 - 16:00 Lunch
16:00 - 17:40 Jesús Vilares Max Rabkin: Ogden's Lemma for ET0L Languages
Daniel Reidenbach and Markus L. Schmid: Patterns with Bounded Treewidth
Mikhail Barash and Alexander Okhotin: Defining Contexts in Context-free Grammars
Laura Bozzelli: Strong Termination for Gap-order Constraint Abstractions of Counter Systems
17:40 - 17:50 Break
17:50 - 18:50 Tomoyuki Yamakami Eugene Asarin: Measuring Information in Timed Languages - Invited Talk

Wednesday, March 7
ATY 8:30 - 10:00 Enrico Formenti Gilles Dowek: Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory (II) - Invited Tutorial
10:00 - 10:15 Break
10:15 - 11:55 G. Michele Pinna Dag Hovland: The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
Jean-Marc Champarnaud, Hadrien Jeanne, and Ludovic Mignot: Approximate Regular Expressions and their Derivatives
Viliam Geffert, Bruno Guillon, and Giovanni Pighizzini: Two-way Automata Making Choices only at the Endmarkers
Holger Bock Axelsen: Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
11:55 - 12:25 Coffee Break
12:25 - 14:05 Gilles Dowek Siva Anantharaman, Christopher Bouchard, Paliath Narendran, and Michael Rusinowitch: Unification Modulo Chaining
Beate Bollig and Tobias Pröger: An Efficient Implicit OBDD-based Algorithm for Maximal Matchings
Travis Gagie, Paweł  Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, and Simon J. Puglisi: A Faster Grammar-based Self-index
Gabriel Ciobanu and G. Michele Pinna: Catalytic Petri Nets are Turing Complete
14:05 - 16:00 Lunch
16:00 - 17:15 Giovanni Pighizzini Tomoyuki Yamakami: One-way Reversible and Quantum Finite Automata with Advice
Ville Salo and Ilkka Törmä: On Stable and Unstable Limit Sets of Finite Families of Cellular Automata
Alberto Dennunzio, Enrico Formenti, and Julien Provillard: Computational Complexity of Rule Distributions of Non-uniform Cellular Automata
17:20 Visit of the city

Thursday, March 8
8:30 - 10:00 Eugene Asarin Rod Downey: A Parameterized Complexity Tutorial (I) - Invited Tutorial
10:00 - 10:15 Break
10:15 - 11:55 Rod Downey Adam Roman: P-NP Threshold for Synchronizing Road Coloring
Arne Meier, Johannes Schmidt, Michael Thomas, and Heribert Vollmer: On the Parameterized Complexity of Default Logic and Autoepistemic Logic
Michal Forišek, Lucia Keller, and Monika Steinová: Advice Complexity of Online Coloring for Paths
Mateus de Oliveira Oliveira: Canonizable Partial Order Generators
11:55 - 12:25 Coffee Break
12:25 - 14:05 Klaus Reinhardt Mathilde Noual: Dynamics of Circuits and Intersecting Circuits
Norbert Hundeshagen and Friedrich Otto: Characterizing the Rational Functions by Restarting Transducers
Ahmet Kara, Thomas Schwentick, and Tony Tan: Feasible Automata for Two-variable Logic with Successor on Data Words
Miroslav Klimoš, Kim G. Larsen, Filip Štefaňák, and Jeppe Thaarup: Nash Equilibria in Concurrent Priced Games
14:05 - 16:00 Lunch
16:00 - 17:15 Miguel A. Alonso Ryo Yoshinaka: Integration of the Dual Approaches in the Distributional Learning of Context-free Grammars
Ziyuan Gao and Frank Stephan: Learnability of Co-r.e. Classes
Michael Geilke and Sandra Zilles: Polynomial-time Algorithms for Learning Typed Pattern Languages
17:15 - 17:30 Break
17:30 - 18:30 Pascal Tesson Jack H. Lutz: The Computer Science of DNA Nanotechnology - Invited Talk

Friday, March 9
8:30 - 10:00 Eugene Asarin Rod Downey: A Parameterized Complexity Tutorial (II) - Invited Tutorial
10:00 - 10:15 Break
10:15 - 11:55 Laura Bozzelli Philip Bille, Inge Li Gørtz, and Jesper Kristensen: Longest Common Extensions via Fingerprinting
Vikraman Arvind and Yadu Vasudev: Isomorphism Testing of Boolean Functions Computable by Constant-depth Circuits
Đurica Nikolić and Fausto Spoto: Automaton-based Array Initialization Analysis
Philip Bille and Morten Stöckel: Fast and Cache-oblivious Dynamic Programming with Local Dependencies
11:55 Closing

Things to consider while preparing the presentation

We notice that for regular papers there are allocated 25 minutes. Our recommendation is to consider the presentation time as 23 minutes and 2 minutes for discussions. There will be one computer available from the organizers and usually materials are loaded during the breaks, to minimize the time between two presentations.

With your agreement, the slides will be published on our web after the conference. It would be nice to have a photo of yourself on the title page. The second page could also contain several pictures with your co-authors, colleagues, home institution. Feel free to use any program to make the presentation, however we expect that Latex will be mostly used. As a final recommendation, regardless the program used for preparation, bring a pdf version of your presentation as well.

The next link could bring some interesting aspects about presentations,

Program translated from TEX by TTHgold, version 4.00.