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 |