Programme

Thursday, April 2

8:00 – 8:45

Registration

8:45 – 9:00

Opening

9:00 – 10:30

BRUNO COURCELLE: Monadic Second­-order Logic for Graphs. Algorithmic and Language Theoretical Applications (I) – Invited Tutorial

10:30 – 10:50

Coffee Break

10:50 – 12:20

NATHALIE BERTRAND, SOPHIE PINCHINAT, JEAN­-BAPTISTE RACLET: Refinement and Consistency of Timed Modal Specifications

OLAF BEYERSDORFF, JOHANNES KÖBLER, SEBASTIAN MÜLLER: Nonde­terministic Instance Complexity and Proof Systems with Advice

BEATE BOLLIG: Larger Lower Bounds on the OBDD Complexity of Integer Multiplication

12:20 – 12:30

Break

12:30 – 14:00

FRANZ BAADER, ANDREAS BAUER, ALWEN TIU: Matching Trace Patterns with Regular Policies

CHRISTOPH BEHLE, ANDREAS KREBS, STEPHANIE REIFFERSCHEID: Non-­Solvable Groups are not in FO+MOD+MÂJ2[REG]

CHRISTIAN GLASSER, A. PAVAN, STEPHEN TRAVERS: The Fault Tolerance of NP­Hard Problems

14:00 – 16:00

Lunch

16:00 – 17:30

RAPHAËL BAILLY, FRANÇOIS DENIS: Absolute Convergence of Rational Se­ries is Semi­-decidable

KIMMO FREDRIKSSON, SZYMON GRABOWSKI: Nested Counters in Bit­-parallel String Matching

TOMOHIRO I, SHUNSUKE INENAGA, HIDEO BANNAI, MASAYUKI TAKEDA: Counting Parameterized Border Arrays for a Binary Alphabet

17:30 – 17:50

Coffee Break

17:50 – 18:50

AUDE LIEFOOGHE, HÉLÈNE TOUZET, JEAN-­STÉPHANE VARRÉ: Self­-overlapping Occurrences and Knuth­-Morris­-Pratt Algorithm for Weighted Matching

ADAM ROMAN: Genetic Algorithm for Synchronization

18:50 – 19:00

Break

19:00 – 20:00

MARKÉTA LOPATKOVÁ, TOMÁŠ HOLAN: Segmentation Charts for Czech – Relations among Segments in Complex Sentences

MAKOTO NAKAMURA, TAKASHI HASHIMOTO, SATOSHI TOJO: Predic­tion of Creole Emergence in Spatial Language Dynamics

Friday, April 3

8:00 – 9:30

BRUNO COURCELLE: Monadic Second­-order Logic for Graphs. Algorithmic and Language Theoretical Applications (II) – Invited Tutorial

9:30 – 9:45

Break

9:45 – 11:15

MATTHIAS BÜCHSE, TORSTEN STÜBER: Monadic Datalog Tree Transducers

OLIVIER GAUWIN, JOACHIM NIEHREN, SOPHIE TISON: Bounded Delay and Concurrency for Earliest Query Answering

FLORENT JACQUEMARD, FRANCIS KLAY, CAMILLE VACHER: Rigid Tree Automata

11:15 – 11:45

Coffee Break

11:45 – 12:45

ANNA KASPRZIK: Two Equivalent Regularizations for Tree Adjoining Gram­mars

NEIL MOORE: The Halting Problem and Undecidability of Document Generation under Access Control for Tree Updates

12:45 – 13:00

Break

13:00 – 14:00

CELINE SCORNAVACCA, VINCENT BERRY, VINCENT RANWEZ: From Gene Trees to Species Trees through a Supertree Approach

LUTZ STRASSBURGER: A Kleene Theorem for Forest Languages

14:00 – 16:00

Lunch

16:00 – 17:30

YOHJI AKAMA: Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory

NINA GIERASIMCZUK: Learning by Erasing in Dynamic Epistemic Logic

RYUICHI MATOBA, MAKOTO NAKAMURA, SATOSHI TOJO: Efficiency of the Symmetry Bias in Grammar Acquisition

17:30 – 18:00

Coffee Break

18:00 – 19:00

FRANK J. BALBACH, THOMAS ZEUGMANN: Recent Developments in Algo­rithmic Teaching – Invited Talk

19:30

Visit to the Old City

Saturday, April 4

9:00 – 10:30

BRUNO COURCELLE: Monadic Second­-order Logic for Graphs. Algorithmic and Language Theoretical Applications (III) – Invited Tutorial

10:30 – 11:00

Coffee Break

11:00 – 12:30

ISABELLE GNAEDIG: Termination of Priority Rewriting

MASAMI ITO, PETER LEUPOLD, VICTOR MITRANA: Bounded Hairpin Completion

JÜRGEN DASSOW, SHERZOD TURAEV: Grammars Controlled by Special Petri Nets

12:30 – 12:45

Break

12:45 – 14:15

PAROSH ABDULLA, GIORGIO DELZANNO, LAURENT VAN BEGIN: A Language­Based Comparison of Extensions of Petri Nets with and without Whole­-Place Operations

TOBIAS BERG, HARALD HEMPEL: Reoptimization of Traveling Salesperson Problems: Changing Single Edge­-Weights

VICTOR MITRANA, BIANCA TRUTHE: On Accepting Networks of Evolution­ary Processors with at Most Two Types of Nodes

14:15

Lunch

Monday, April 6

8:30 – 9:30

MARKUS HOLZER, MARTIN KUTRIB: Descriptional and Computational Complexity of Finite Automata (I) – Invited Tutorial

9:30 – 9:45

Break

9:45 – 11:15

BERNARD BOIGELOT, JEAN­-FRANÇOIS DEGBOMONT: Partial Projection of Sets Represented by Finite Automata, with Application to State-­Space Visual­ization

PASCAL CARON, JEAN­-MARC CHAMPARNAUD, LUDOVIC MIGNOT: Multi­-tilde Operators and their Glushkov Automata

CYRIL NICAUD: On the Average Size of Glushkov’s Automata

11:15 – 11:45

Coffee Break

11:45 – 12:45

ELENA PRIBAVKINA, EMANUELE RODARO: Finitely Generated Synchroniz­ing Automata

P. VIJAY SUMAN, PARITOSH PANDYA: Determinization and Expressiveness of Integer Reset Timed Automata with Silent Transitions

12:45 – 13:00

Break

13:00 – 14:00

SICCO VERWER, MATHIJS DE WEERDT, CEES WITTEVEEN: One­-clock De­terministic Timed Automata are Efficiently Identifiable in the Limit

ALEXEI LISITSA, IGOR POTAPOV, RAFIQ SALEH: Automata on Gauss Words

14:00 – 16:00

Lunch

16:00 – 17:30

FRANCINE BLANCHET­-SADRI, EMILY ALLEN, CAMERON BYRUM, RO­BERT MERCAS: How Many Holes Can an Unbordered Partial Word Contain?

FRANCINE BLANCHET-­SADRI, ROBERT MERCAS, ABRAHAM RASHIN, ELARA WILLETT: An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms

MICHELANGELO BUCCI, ALESSANDRO DE LUCA: On a Family of Morphic Images of Arnoux­-Rauzy Words

17:30 – 18:00

Coffee Break

18:00 – 19:00

SANJAY JAIN: Hypothesis Spaces for Learning – Invited Talk

19:30

Visit to the City Hall

Tuesday, April 7

8:30 – 9:30

MARKUS HOLZER, MARTIN KUTRIB: Descriptional and Computational Complexity of Finite Automata (II) – Invited Tutorial

9:30 – 9:45

Break

9:45 – 11:15

GIANPIERO CATTANEO, ALBERTO DENNUNZIO, ENRICO FORMENTI, JULIEN PROVILLARD: Non­-Uniform Cellular Automata

ADAM CLARRIDGE, KAI SALOMAA: A Cryptosystem Based on the Compo­sition of Reversible Cellular Automata

GALINA JIRÁSKOVÁ, GIOVANNI PIGHIZZINI: Converting Self-­Verifying Automata into Deterministic Automata

11:15 – 11:45

Coffee Break

11:45 – 12:45

SERGEY AFONIN, DENIS GOLOMAZOV: Minimal Union­-free Decomposi­tions of Regular Languages

HENNING BORDIHN, MARKUS HOLZER, MARTIN KUTRIB: Undecidabil­ity of Operation Problems for T0L Languages and Subclasses

12:45 – 13:00

Break

13:00 – 14:00

PAUL SALIMOV: Constructing Infinite Words of Intermediate Arithmetical Complexity

WATARU MATSUBARA, KAZUHIKO KUSANO, HIDEO BANNAI, AYUMI SHINOHARA: A Series of Run­-rich Strings

14:00 – 16:00

Lunch

16:00 – 17:00

JIAMOU LIU, MIA MINNES: Analysing Complexity in Classes of Unary Au­tomatic Structures

JORDI LLULL-­CHAVARRÍA, ÓSCAR VALERO: An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words

17:00 – 17:30

Coffee Break

17:30 – 18:30

YO-SUB HAN, KAI SALOMAA, SHENG YU: State Complexity of Combined Operations for Prefix­-Free Regular Languages

NUTAN LIMAYE, MEENA MAHAJAN: Membership Testing: Removing Extra Stacks from Multi­-stack Pushdown Automata

18:30 – 18:45

Break

18:45 – 19:45

KAI SALOMAA: State Complexity of Nested Word Automata – Invited Talk

Wednesday, April 8

8:30 – 9:30

MARKUS HOLZER, MARTIN KUTRIB: Descriptional and Computational Complexity of Finite Automata (III) – Invited Tutorial

9:30 – 9:45

Break

9:45 – 11:15

TOMÁŠ MASOPUST: A Note on the Generative Power of Some Simple Variants of Context­-Free Grammars Regulated by Context Conditions

KAORU ONODERA: New Morphic Characterizations of Languages in Chom­sky Hierarchy using Insertion and Locality

DANA PARDUBSKÁ, MARTIN PLÁTEK, FRIEDRICH OTTO: On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Au­tomata

11:15 – 11:45

Coffee Break

11:45 – 12:45

PAOLA BONIZZONI, CLAUDIO FERRETTI, ANTHONATH ROSLIN SAGAYA MARY, GIANCARLO MAURI: Picture Languages Generated by Assembling Tiles

NICOLAS OLLINGER: Tiling the Plane with a Fixed Number of Polyominoes

12:45 – 13:00

Break

13:00 – 14:30

JANUSZ BRZOZOWSKI, JEFFREY SHALLIT, ZHI XU: Decision Problems for Convex Languages

BENJAMIN CARLE, PALIATH NARENDRAN: On Extended Regular Expres­sions

KEES HEMERIK: Towards a Taxonomy for ECFG and RRPG Parsing

14:30

Closing