Accepted Papers

   
Full Papers

Janusz Brzozowski and Hellis Tamm

Quotient Complexities of Atoms of Regular Languages

Francine Blanchet-Sadri, Yang Jiao and John Machacek

Squares in Binary Partial Words

Alexandre Blondin Massé, Sébastien Gaboury and Sylvain Hallé

Pseudoperiodic words

Zoltan Esik and Satoshi Okawa

 On context-free languages of scattered words

Viliam Geffert and Dana Pardubska

Unary Coded NP-Complete Languages in ASPACE(loglog n)

Daniel Prusa and Frantisek Mraz

Two-dimensional Sgraffito Automata

Marie-Pierre Béal, Jean-Marc Champarnaud, Jean-Philippe Dubernard, Hadrien Jeanne and Sylvain Lombardy

Decidability of geometricity of regular languages

Matthias Büchse, Andreas Maletti and Heiko Vogler

Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars

Alberto Dennunzio, Enrico Formenti and Julien Provillard

Acceptance conditions for $\omega$-languages

Christos Kapoutsis and Nans Lefebvre

Analogs of Fagin's Theorem for Small Nondeterministic Finite Automata

Martin Kutrib, Andreas Malcher and Matthias Wendlandt

States and Heads Do Count For Unary Multi-Head Finite Automata

Friedrich Otto

On Centralized PC Grammar Systems with Context-Sensitive Components

Giovanna Lavado, Giovanni Pighizzini and Shinnosuke Seki

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata

Andreas Krebs and Klaus-Joern Lange

Dense Completeness

Yo-Sub Han, Sang-Ki Ko and Kai Salomaa.

Computing the edit-distance between a regular language and a context-free language

Olivier Carton

Two-way transducers with a two-way output tape

Florin Manea, Mike Müller and Dirk Nowotka

The Avoidability of Cubes under Permutations

Szilard Zsolt Fazekas, Robert Mercas and Kayoko Shikishima-Tsuji

Hairpin completion with bounded stem-loop

Aniruddh Gandhi, Bakhadyr Khoussainov and Jiamou Liu

On state complexity of finite word and tree languages

Michael Hoffmann, Derek Holt, Matt Owens and Rick Thomas

Semigroups with a context-free word problem

Haiming Chen and Ping Lu

Checking Determinism of Regular Expressions with Counting

Juhani Karhumäki, Svetlana Puzynina and Aleksi Saarela

Fine and Wilf's Theorem for $k$-Abelian Periods

Tommi Lehtinen and Alexander Okhotin

Homomorphisms preserving deterministic context-free languages

Mathieu Caralp, Pierre-Alain Reynier and Jean-Marc Talbot

Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness

Michaël Cadilhac, Alain Finkel and Pierre Mckenzie.

Unambiguous Constrained Automata

Alexander Okhotin

Non-erasing variants of the Chomsky--Schützenberger theorem

Markus Holzer, Sebastian Jakobi and Ian McQuillan

General Derivations with Synchronized Context-Free Grammars

Ondrej Klima and Libor Polak

Biautomata for k-Piecewise Testable Languages

Daniel Reidenbach and Markus L. Schmid

Regular and Context-Free Pattern Languages Over Small Alphabets

Hossein Nevisi and Daniel Reidenbach

Morphic Primitivity and Alphabet Reductions

Markus Holzer and Sebastian Jakobi

From Equivalence to Almost-Equivalence, and Beyond---Minimizing Automata With Errors

Markus L. Schmid

Inside the Class of REGEX Languages

Galina Jiraskova and Jeffrey Shallit

The state complexity of star-complement-star

Adrien Boiret, Aurélien Lemay and Joachim Niehren.

Learning Rational Functions

 

 

Short  Papers

Ilkka Törmä and Ville Salo

Geometry and Dynamics of the Besicovitch and Weyl Spaces

Nils Erik Flick and Manfred Kudlek

A Hierarchy of Languages with Catenation and Shuffle

Jeroen Ketema and Jakob Grue Simonsen

Characterizing Languages by Normalization and Termination in String Rewriting

 Laura Giambruno, Sabrina Mantaci, Jean Néraud and Carla Selmi

A generalization of Girod's bidirectional decoding method to codes with a finite deciphering delay