Program

8:00 – 9:00 Registration

9:00 – 9:15 Opening

9:15 – 10:45

Tomáš Masopust and Alexander Meduna: Descriptional Complexity of Grammars Regulated by Context Conditions

Guangwu Liu, Carlos Martín-Vide, Arto Salomaa and Sheng Yu: State Complexity of Basic Operations Combined with Reversal

Henning Fernau and Jürgen Dassow: Comparison of Some Descriptional Complexities of 0L Systems Obtained by a Unifying Approach

10:45 – 11:15 Coffee Break

11:15 – 12:15

Vinay Choudhary, Anand Kumar Sinha and Somenath Biswas: Universality for Nondeterministic Logspace

Hermann Gruber and Markus Holzer: Computational Complexity of NFA Minimization for Finite and Unary Languages

12:15 – 12:30 Break

12:30 – 14:00
Tutorial

Volker Diekert:
Equations: From Words to Graph Products (I)

14:00 – 16:00 Lunch

16:00 – 17:30

Grigoriy Povarov: Descriptive Complexity of the Hamming Neighborhood of a Regular Language

Baptiste Blanpain, Jean-Marc Champarnaud and Jean-Philippe Dubernard: Geometrical Languages

Olivier Bodini, Thomas Fernique and Eric Rémila: A Characterization of Flip-accessibility for Rhombus Tilings of the Whole Plane

17:30 – 18:00 Coffee Break

18:00 – 19:30

Bernd Borchert and Klaus Reinhardt: Deterministically and Sudoku-Deterministically Recognizable Picture Languages

Ralf Stiebe: Slender Siromoney Matrix Languages

Kazuya Ogasawara and Satoshi Kobayashi: Stochastically Approximating Tree Grammars by Regular Grammars and Its Application to Faster ncRNA Family Annotation

Friday, March 30

8:45 – 10:15

Andreas Maletti: Compositions of Extended Top-down Tree Transducers

Ekaterina Komendantskaya: First-order Deduction in Neural Networks

Pál Dömösi: Automata Networks without any Letichevsky Criteria

10:15 – 10:45 Coffee Break

10:45 – 12:15

Henning Bordihn and György Vaszil: On Leftmost Derivations in CD Grammar Systems

Suna Bensch: An Approach to Parallel Mildly Context-Sensitive Grammar Formalisms

Yurii Rogozhin, Carlos Martín-Vide and Artiom Alhazov: Networks of Evolutionary Processors with two Nodes are Unpredictable

12:15 – 12:30 Break

12:30 – 14:00
Tutorial

Volker Diekert:
Equations: From Words to Graph Products (II)

14:00 – 16:00 Lunch

16:00 – 17:30

Victor Selivanov: Classifying Omega-Regular Partitions

Paolo Boldi, Violetta Lonati, Roberto Radicioni and Santini Massimo: The Number of Convex Permutominoes

Pawel Baturo and Wojciech Rytter: Occurrence and Lexicographic Properties of Standard Sturmian Words

17:30 – 18:00 Coffee Break

18:00 – 19:00
Invited Talk

Neil Immerman:
Nested Words

19:30 Visit to the Old City

Monday, April 2

9:00 – 10:30

Francine Blanchet-Sadri, Kevin Corcoran and Jenell Nyberg: Fine and Wilf's Periodicity Result on Partial Words and Consequences

Costas Iliopoulos, Bořivoj Melichar, Jan Šupol and Inuka Jayasekera: Weighted Degenerated Approximate Pattern Matching

Krystyna Stawikowska and Edward Ochmański: On Star-Free Trace Languages and their Lexicographic Representations

10:30 – 11:00 Coffee Break

11:00 – 12:30

Zoltán L. Németh: On the Regularity of Binoid Languages: A Comparative Approach

Markus Lohrey and Benjamin Steinberg: The Submonoid and Rational Subset Membership Problems for Graph Groups

Camilo Thorne: Categorial Module Grammars of Bounded Size have Finite Bounded Density

12:30 – 12:45 Break

12:45 – 13:45
Tutorial

Erich Grädel:
Infinite Games (I)

13:45 – 15:45 Lunch

15:45 – 17:15

Mathieu Poudret, Jean-Paul Comet, Pascale Le Gall, Agnès Arnould and Philippe Meseure: Topology-based Geometric Modelling for Biological Cellular Processes

Farid Ablayev and Aida Gainutdinova: Classical Simulation Complexity of Quantum Branching Programs

Martin Kochol, Nada Krivoňáková, Silvia Smejová and Katarína Šranková: Reductions of Matrices Associated with Nowhere-Zero Flows

17:15 – 17:45 Coffee Break

17:45 – 18:45

Session Chair:
Reinhard Rapp

Juntae Yoon and Seonho Kim: Rule-based Word Spacing in Korean Based on Lexical Information Extracted from a Corpus

Julien Bourdaillet and Jean-Gabriel Ganascia: Practical Block Sequence Alignment with Moves

18:45 – 19:00 Break

19:00 – 20:00

Invited Talk

Session Chair:
Sheng Yu

Helmut Jürgensen:
Synchronization

Tuesday, April 3

9:00 – 10:30

Session Chair:
Alexander Okhotin

Pavlos Antoniou, Maxime Crochemore, Costas Iliopoulos and Pierre Peterlongo: Application of Suffix Trees for the Acquisition of Common Motifs with Gaps in a Set of Strings

František Mráz, Friedrich Otto and Martin Plátek: Free Word-Order and Restarting Automata

Martin Kutrib and Jens Reimann: Succinct Description of Regular Languages by Weak Restarting Automata

10:30 – 11:00 Coffee Break

11:00 – 12:30

Session Chair:
Holger Petersen

Hartmut Messerschmidt and Friedrich Otto: On Determinism Versus Non-Determinism for Restarting Automata

Martin Kutrib and Andreas Malcher: Fast Reversible Language Recognition Using Cellular Automata

Pietro Di Lena and Luciano Margara: Computational Complexity of Dynamical Systems: the Case of Cellular Automata

12:30 – 12:45 Break

12:45 – 13:45
Tutorial

Session Chair:
Victor Mitrana

Erich Grädel:
Infinite Games (II)

13:45 – 15:45 Lunch

15:45 – 17:15

Session Chair:
Friedrich Otto

Christos Nomikos and Panos Rondogiannis: Locally Stratified Boolean Grammars

Alexander Okhotin: Unambiguous Boolean Grammars

Yo-Sub Han and Derick Wood: Generalizations of One-Deterministic Regular Languages

17:15 – 17:45 Coffee Break

17:45 – 18:45

Session Chair:
Nissim Francez

Franz Baader, Jan Hladik and Rafael Peñaloza: SI! Automata Can Show PSPACE Results for Description Logics

Liviu P. Dinu, Radu Gramatovici and Florin Manea: On the Syllabification of Words via Go-Through Automata

18:45 – 19:00 Break

19:00 – 20:00
Invited Talk

Session Chair:
Erich Grädel

Nissim Francez and Michael Kaminski:
Extensions of Pregroup Grammars and Their Correlated Automata

20:30 Visit to the City Hall

9:15 – 10:45

Session Chair:
Helmut Jürgensen

Deian Tabakov and Moshe Vardi: Model Checking Buechi Specifications

Benedikt Bollig and Dietrich Kuske: Muller Message-Passing Automata and Logics

Pavel Martjugin: A Series of Slowly Synchronizable Automata with a Zero State Over a Small Alphabet

10:45 – 11:15 Coffee Break

11:15 – 12:15

Session Chair:
Jürgen Dassow

Gennaro Parlato, Salvatore La Torre, Margherita Napoli and Mimmo Parente: Verification of Succinct Hierarchical State Machines

Miklós Krész: Nondeterministic Soliton Automata with a Single External Vertex

12:15 – 12:30 Break

12:30 – 13:30
Tutorial

Session Chair:
Victor Mitrana

Erich Grädel:
Infinite Games (III)

13:30 Closing