LATA 2016: call for participation*To be removed from our mailing list, please respond to this message with UNSUBSCRIBE in the

subject line*


**********************************************************************************


10th INTERNATIONAL CONFERENCE ON LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS


LATA 2016


Prague, Czech Republic


March 14-18, 2016


Organized by:


Department of Theoretical Computer Science

Faculty of Information Technology

Czech Technical University in Prague


and


Research Group on Mathematical Linguistics (GRLMC)

Rovira i Virgili University


http://grammars.grlmc.com/lata2016/


**********************************************************************************


PROGRAM



Monday, March 14



08:55 - 09:40    Registration


09:40 - 09:55    Opening


09:55 - 10:45    Avrim Blum: Reconstructing Preferences from Opaque Transactions - Invited

Lecture


10:45 - 11:15    Coffee Break


11:15 - 12:30


Franz Baader, Andreas Ecke: Reasoning with Prototypes in the Description Logic ALC using

Weighted Tree Automata


Parvaneh Babari, Nicole Schweikardt: +ω-Picture Languages Recognizable by Büchi-Tiling

Systems


Devendra Bhave, Vrunda Dave, Krishna Shankara Narayanan, Ramchandra Phawade, Ashutosh

Trivedi: A Logical Characterization for Dense-Time Visibly Pushdown Automata


12:30 - 14:00    Lunch


14:00 - 15:15


Dana Fisman: A Complexity Measure on Büchi Automata


Vahid Hashemi, Holger Hermanns, Lei Song, K. Subramani, Andrea Turrini, Piotr Wojciechowski:

Compositional Bisimulation Minimization for Interval Markov Decision Processes


Heiko Vogler, Manfred Droste, Luisa Herrmann: A Weighted MSO Logic with Storage Behaviour

and its Büchi-Elgot-Trakhtenbrot Theorem


15:15 - 15:30    Break


15:30 - 16:45


Rajeev Alur, Dana Fisman: Colored Nested Words


Martin Kutrib, Andreas Malcher, Matthias Wendlandt: Input-Driven Queue Automata with

Internal Transductions


Klaus Meer, Ameen Naif: Periodic Generalized Automata over the Reals



Tuesday, March 15



09:00 - 09:50     Martin Grohe: Tangles and Connectivity in Graphs - Invited Lecture


09:50 - 10:05    Break


10:05 - 11:20


Rick Smetsers, Joshua Moerman, David N. Jansen: Minimal Separating Sequences for All Pairs

of States


Martin Sulzmann, Peter Thiemann: Forkable Regular Expressions


Hélène Touzet: On the Levenshtein Automaton and the Size of the Neighbourhood of a Word


11:20 - 11:50    Coffee Break


11:50 - 13:05


Alexandre Blondin Massé, Mélodie Lapointe, Hugo Tremblay: Parallelogram Morphisms and

Circular Codes


Ananda Chandra Nayak, Amit K. Srivastava: On Del-Robust Primitive Partial Words with One

Hole


Maxime Crochemore, Roman Kolpakov, Gregory Kucherov: Optimal Bounds for Computing α-gapped

Repeats


13:05 - 14:35    Lunch


14:35 - 15:50


Kazuyuki Amano: On XOR Lemma for Polynomial Threshold Weight and Length


Yu Chen, Xiaotie Deng, Ziwei Ji, Chao Liao: The Beachcombers' Problem: Walking and Searching

from an Inner Point of a Line


Silke Czarnetzki, Andreas Krebs: Using Duality in Circuit Complexity


15:50 - 16:05    Break


16:05 - 17:20


Gabriel Istrate, Cosmin Bonchiş, Liviu Dinu: The Minimum Entropy Submodular Set Cover

Problem


Orna Kupferman, Sarai Sheinvald: On the Capacity of Capacitated Automata


Holger Spakowski: On Limited Nondeterminism and ACC Circuit Lower Bounds



Wednesday, March 16



09:00 - 09:50    Frank Wolter: Automata for Ontologies - Invited Lecture


09:50 - 10:05    Break


10:05 - 11:20


Kunihiro Wasa, Katsuhisa Yamanaka, Hiroki Arimura: The Complexity of Induced Tree

Reconfiguration Problems


Stefano Crespi Reghizzi, Pierluigi San Pietro: The Missing Case in Chomsky-Schützenberger

Theorem


Séverine Fratani, El Makki Voundy: Homomorphic Characterizations of Indexed Languages


11:20 - 11:50    Group Photo and Coffee Break


11:50 - 13:05


Makoto Kanazawa: Ogden's Lemma, Multiple Context-Free Grammars, and the Control Language

Hierarchy


Sebastian Berndt, Rüdiger Reischuk: Steganography Based on Pattern Languages


Guen-Hae Kim, Sang-Ki Ko, Yo-Sub Han: Inferring a Relax NG Schema from XML Documents


13:05 - 14:35    Lunch


14:35 - 15:50


Atsuyoshi Nakamura, David P. Helmbold, Manfred K. Warmuth: Noise Free Multi-armed Bandit

Game


Johannes Blum, Frank Drewes: Properties of Regular DAG Languages


Adrien Boiret: Normal Form on Linear Tree-to-Word Transducers


16:00 - 18:00    Touristic Visit



Thursday, March 17



09:00 - 09:50    Romain Brenguier, Lorenzo Clemente, Paul Hunter, Guillermo A. Pérez, Mickael

Randour, Jean-François Raskin, Ocan Sankur, Mathieu Sassolas: Non-zero Sum Games for

Reactive Synthesis - Invited Lecture


09:50 - 10:05    Break


10:05 - 11:20


Manfred Droste, Zoltán Fülöp, Doreen Götze: A Kleene Theorem for Weighted Tree Automata over

Tree Valuation Monoids


Nadia Labai, Johann A. Makowsky: Hankel Matrices for Weighted Visibly Pushdown Automata


Johannes Osterholzer, Toni Dietze, Luisa Herrmann: Linear Context-Free Tree Languages and

Inverse Homomorphisms


11:20 - 11:50    Coffee Break


11:50 - 13:05


Paul C. Bell, Shang Chen, Lisa Jackson: Scalar Ambiguity and Freeness in Matrix Semigroups

over Bounded Languages


Tatiana Baginová Jajcayová: The Word Problem for HNN-Extensions of Free Inverse Semigroups


Henrik Björklund, Frank Drewes, Petter Ericson: Between a Rock and a Hard Place - Uniform

Parsing for Hyperedge Replacement DAG Grammars


13:05 - 14:35    Lunch


14:35 - 16:05    Giovanni Pighizzini: Restricted Turing Machines and Language Recognition (I)

- Invited Tutorial


16:05 - 16:20    Break


16:20 - 17:10


Sanguthevar Rajasekaran, Marius Nicolae: An Error Correcting Parser for Context-Free

Grammars that Takes Less than Cubic Time


Nathalie Bertrand, Serge Haddad, Engel Lefaucheux: Accurate Approximate Diagnosability of

Stochastic Systems



Friday, March 18



09:00 - 10:30    Giovanni Pighizzini: Restricted Turing Machines and Language Recognition

(II) - Invited Tutorial


10:30 - 10:45    Break


10:45 - 11:35


Isabela Dramnesc, Tudor Jebelean, Sorin Stratulat: Proof-Based Synthesis of Sorting

Algorithms for Trees


Holger Bock Axelsen, Markus Holzer, Martin Kutrib, Andreas Malcher: Reversible Shrinking

Two-pushdown Automata


11:35 - 12:05    Coffee Break


12:05 - 12:55


Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Antonio E. Porreca: Reachability in

Resource-Bounded Reaction Systems


Hans-Jörg Kreowski, Sabine Kuske, Aaron Lye: Canonical Multi-target Toffoli Circuits


12:55 - 13:10    Closing