16th International Workshop on
Descriptional Complexity of Formal Systems

August 5-8, 2014
Department of Mathematics and Statistics, University of Turku
Turku, Finland


Invited Speakers * Important Dates * Topics of Interest * Submission * Discussion/Open Problems Session * Programme Committee * Steering Committee * Venue & Travel * Organizing Committee * Contacts


Preliminary programme

Monday, August 4

18:00 – 21:00

Welcome snacks

 

 

Tuesday, August 5

08:30 – 09:15

Registration

09:15 – 09:30

Opening

 

Session I (chairman: Juhani Karhumäki)

09:30 – 10:30

Oscar Ibarra

Automata with reversal-bounded counters: a survey

10:30 – 11:00

Coffee break

 

Session II (chairman: Martin Kutrib)

11:00 – 11:30

Prateek Karandikar, Philippe Schnoebelen

On the state complexity of closures and interiors of regular languages with subwords

11:30 – 12:00

Janusz Brzozowski, Gareth Davies

Most complex regular right-ideal languages

12:00 – 12:30

Alexandros Palioudakis, Kai Salomaa, Selim Akl

State complexity of unary language operations for NFAs with limited nondeterminism

12:30 – 14:00

Lunch

 

Session III (chairman: Alexander Okhotin)

14:00 – 15:00

Manfred Kufleitner

Star-free languages and local divisors

15:00 – 15:30

Mai Gehrke, Andreas Krebs, Jean-Éric Pin

From ultrafilters on words to the expressive power of a fragment of logic

15:30 – 16:00

Coffee break

 

Session IV (chairman: Giovanni Pighizzini)

16:00 – 16:30

Markus Holzer, Sebastian Jakobi

Boundary sets of regular and context-free languages

16:30 – 17:00

Daniel Průša

Non-recursive trade-offs between two-dimensional automata and grammars

17:00 – 17:30

Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Regularity and size of set automata

 

 

19:00 – 20:30

Reception at Turku City Hall

 

 

Wednesday, August 6

 

Session V (chairman: Jarkko Kari)

09:00 – 10:00

Nikolay Vereshchagin

Aperiodic tilings by right triangles

10:00 – 10:30

Coffee break

 

Session VI (chairman: Jean-Éric Pin)

10:30 – 11:00

Giovanna Lavado, Giovanni Pighizzini, Shinnosuke Seki

Operational state complexity under Parikh equivalence

11:00 – 11:30

Marina Maslennikova

Complexity of checking whether two automata are synchronized by the same language

11:30 – 12:00

Szabolcs Iván, Ádám D. Lelkes, Judit Nagy-György, Balázs Szörényi, György Turán

Biclique coverings, rectifier networks and the cost of epsilon-removal

12:00 – 13:30

Lunch

 

Session VII (chairman: Janusz Brzozowski)

13:30 – 14:00

Jozef Jirásek, Galina Jirásková, Monika Krausová, Peter Mlynarčík, Juraj Šebej

Prefix-free Languages: right quotient and reversal

14:00 – 14:30

Da-Jung Cho, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa

State complexity of inversion operations

14:30 – 15:00

Daniel Goč, Kai Salomaa

Computation width and deviation number

15:00 – 15:30

Coffee break

 

Session VIII (chairman: Markus Holzer)

15:30 – 16:00

Andreas Krebs, Michael Ludwig, Olga Dorzweiler, Thomas Flamm

Positive and negative proofs for circuits and branching programs

16:00 – 16:30

Jan Janoušek, Martin Poliak, Bořivoj Melichar

A full and linear index of a tree for tree patterns

16:30 – 17:00

Angelo Borsotti, Luca Breveglieri, Stefano Crespi Reghizzi, Angelo Morzenti

Complexity of extended vs. classic LR parsers

 

 

17:30 – 18:30

General meeting

 

 

Thursday, August 7

 

Session IX (chairman: Mika Hirvensalo)

09:00 – 10:00

Andris Ambainis

Recent developments in quantum algorithms and complexity

10:00 – 10:30

Coffee break

 

Session X (chairman: Andris Ambainis)

10:30 – 11:00

Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, Abuzer Yakaryılmaz

Very narrow quantum OBDDs and width hierarchies for classical OBDD

11:00 – 11:30

Farid Ablayev, Marat Ablayev

Quantum hashing via epsilon-universal hashing constructions and Freivalds fingerprinting schemas

11:30 – 12:00

Viliam Geffert, Abuzer Yakaryılmaz

Classical automata on promise problems

12:00 – 13:30

Lunch

14:00 – 23:00

Social event

 

 

Friday, August 8

 

Session XI (chairman: TBA)

09:00 – 09:30

Friedrich Otto

On the descriptional complexity of deterministic ordered restarting automata

09:30 – 10:00

Holger Petersen

A note on pushdown automata systems

10:00 – 10:30

Balagopal Komarath, Jayalal Sarma, Sunil K.S.

On the complexity of L-reachability

10:30 – 11:00

Coffee break

 

Session XII (chairman: Kai Salomaa)

11:00 – 11:30

Sang-Ki Ko, Ha-Rim Lee, Yo-Sub Han

State complexity of regular tree languages for tree pattern matching

11:30 – 12:00

Galina Jirásková, Peter Mlynarčík

Complement on prefix-free, suffix-free, and non-returning NFA languages

12:00 – 13:30

Lunch

 

Session XIII (chairwoman: Erzsébet Csuhaj-Varjú)

13:30 – 14:00

Sergiu Ivanov, Elisabeth Pelz, Sergey Verlan

Small universal non-deterministic Petri nets with inhibitor arcs

14:00 – 14:30

Artiom Alhazov, Bogdan Aman, Rudolf Freund, Gheorghe Păun

Matter and anti-matter in membrane systems

14:30 – 15:00

Enrico Formenti, Luca Manzoni, Antonio E. Porreca

Cycles and global attractors of reaction systems