Published: 21st May 2014
DOI: 10.4204/EPTCS.151
ISSN: 2075-2180

EPTCS 151

Proceedings 14th International Conference on
Automata and Formal Languages
Szeged, Hungary, May 27-29, 2014

Edited by: Zoltán Ésik and Zoltán Fülöp
Preface
Zoltán Ésik and Zoltán Fülöp
Invited Presentation: Saturation algorithms for model-checking pushdown systems
Arnaud Carayol and Matthew Hague		1
Invited Presentation: From Finite Automata to Regular Expressions and Back—A Summary on Descriptional Complexity
Hermann Gruber and Markus Holzer		25
Invited Presentation: On Varieties of Automata Enriched with an Algebraic Structure (Extended Abstract)
Ondřej Klíma		49
Invited Presentation: Decision Problems for Deterministic Pushdown Automata on Infinite Words
Christof Löding		55
Invited Presentation: Equivalence Problems for Tree Transducers: A Brief Survey
Sebastian Maneth		74
Grammars with two-sided contexts
Mikhail Barash and Alexander Okhotin		94
Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching
Martin Berglund, Frank Drewes and Brink van der Merwe		109
Measuring Communication in Parallel Communicating Finite Automata
Henning Bordihn, Martin Kutrib and Andreas Malcher		124
Languages of lossless seeds
Karel Břinda		139
Maximally Atomic Languages
Janusz Brzozowski and Gareth Davies		151
Simplifying Nondeterministic Finite Cover Automata
Cezar Câmpeanu		162
On the Expressiveness of TPTL and MTL over ω-Data Words
Claudia Carapelle, Shiguang Feng, Oliver Fernández Gil and Karin Quaas		174
On Determinism and Unambiguity of Weighted Two-way Automata
Vincent Carnino and Sylvain Lombardy		188
Operations on Automata with All States Final
Kristína Čevorová, Galina Jirásková, Peter Mlynárčik, Matúš Palmovský and Juraj Šebej		201
Commutative Languages and their Composition by Consensual Methods
Stefano Crespi Reghizzi and Pierluigi San Pietro		216
Similarity density of the Thue-Morse word with overlap-free infinite binary words
Chen Fei Du and Jeffrey Shallit		231
Cooperating Distributed Grammar Systems of Finite Index Working in Hybrid Modes
Henning Fernau, Rudolf Freund and Markus Holzer		246
Representations of Circular Words
László Hegedüs and Benedek Nagy		261
More Structural Characterizations of Some Subregular Language Families by Biautomata
Markus Holzer and Sebastian Jakobi		271
Buffered Simulation Games for Büchi Automata
Milka Hutagalung, Martin Lange and Etienne Lozes		286
Synchronizing weighted automata
Szabolcs Iván		301
Hyper-Minimization for Deterministic Weighted Tree Automata
Andreas Maletti and Daniel Quernheim		314
K-Position, Follow, Equation and K-C-Continuation Tree Automata Constructions
Ludovic Mignot, Nadia Ouali Sebti and Djelloul Ziadi		327
Boolean Circuit Complexity of Regular Languages
Maris Valdats		342
A Simple Character String Proof of the "True but Unprovable" Version of Gödel's First Incompleteness Theorem
Antti Valmari		355
Subset Synchronization of Transitive Automata
Vojtěch Vorel		370

Preface

The 14th International Conference Automata and Formal Languages (AFL 2014) was held in Szeged, Hungary, from the 27th to the 29th of May, 2014. The conference was organized by the Department of Foundations of Computer Science of the University of Szeged. Topics of interest covered the theory and applications of automata and formal languages and related areas.

The scientific program consisted of invited lectures by

and 21 short presentations.

This volume contains the texts of the invited lecturers and the 21 papers selected by the International Program Committee from a total of 33 submissions. We would like to thank everybody who submitted a paper to the conference.

The members of the International Program Committee were

We thank all members of the Program Committee and their subreferees who assisted in the selection of the papers. Special thanks go to the Szent-Györgyi Albert Agora for providing us with the conference facilities, and to our sponsors, the John von Neumann Computer Society and the Szeged Software Zrt, and the Institute of Informatics of the University of Szeged.

Local organization

AFL Steering Committee

List of subreviewers

Dragana Bajic, A. Baskar, Beatrice Berard, Mikhail Berlinkov, Johanna Björklund, Benedikt Bollig, Péter Burcsi, Michaël Cadilhac, Maxime Crochemore, Judit Csima, Flavio D'Alessandro, Attila Egri-Nagy, Szilárd Zsolt Fazekas, Gabriele Fici, Anna Frid, Yo-Sub Han, Markus Holzer, Norbert Hundeshagen, Szabolcs Iván, Sebastian Jakobi, Artur Jeż, Antonios Kalampakas, Stefan Kiefer, Manfred Kufleitner, Peter Leupold, Andreas Malcher, Eleni Mandrali, Giovanni Manzini, Katja Meckel, Victor Mitrana, Frantisek Mraz, Benedek Nagy, Laurent Noé, Beatrice Palano, Svetlana Puzynina, George Rahonis, Gwenaël Richomme, Chloé Rispal, Benoît Rittaud, Aleksi Saarela, Moshe Schwartz, Juraj Sebej, Shinnosuke Seki, Simoni Shah, Magnus Steinby, Vaishnavi Sundararajan, Louis-Marie Traonouez, Mikhail Volkov, Igor Walukiewicz, Qichao Wang, Yuan-Fang Wang, Abuzer Yakaryilmaz, Niklas Zechner, Georg Zetzsche.