Program

10:30	Anton Pirogov A unified approach to Büchi determinisation (abstract)
10:40	Pierre Ganty Algorithms for inclusion into a regular language (abstract)
10:50	Bruno Guillon Determinizing two-way automata with linear-time Turing machines (abstract)

10:30-11:10 Session 6B

Logic

Chair:

Karin Quaas

Location: H 2013

10:30	André Frochaux An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree (abstract)
10:40	Amazigh Amrane Logic and rational languages of scattered and countable series-parallel posets (abstract)
10:50	Edon Kelmendi Expressing Unboudedness in MSO + nabla (abstract)
11:00	Marcin Przybyłko On Computing the Measures of First-Order Definable Sets of Trees (abstract)

10:30-11:10 Session 6C

Parity Games

Chair:

Véronique Bruyère

Location: H 2032

10:30	Karoliina Lehtinen Solving parity games in quasi-polynomial time -- a logician's approach (abstract)
10:40	Paweł Parys Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games (abstract)
10:50	Thomas Colcombet Universal parity graphs and lower bounds for parity games (abstract)
11:00	Tom van Dijk Solving parity games with tangles (abstract)

11:20-12:00 Session 7: Spotlight

Chair:

Catalin Dima

Location: H 3010

11:20

Laura Kovács

Symbol Elimination for Program Analysis (abstract)

12:00-13:30Lunch break

13:30-15:20 Session 8: Invited Session

Logic and Learning

Chair:

Martin Grohe

Location: H 3010

13:30	Kristian Kersting The Automatic Data Scientist: Making Data Science Easier using High-level Languages, Fractional Automorphisms, and Arithmetic Circuits (abstract)
14:20	Daniel Neider Learning Linear Temporal Properties (abstract)
14:50	Dan Olteanu Learning Models over Relational Databases (abstract)

15:20-15:50Coffee break

15:50-16:30 Session 9A

Logic and Graphs

Chair:

Nicole Schweikardt

Location: H 3010

15:50	Joanna Ochremiak Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem (abstract)
16:00	Oleg Verbitsky On the First-Order Complexity of Subgraph Isomorphism (abstract)
16:10	Sandra Kiefer Distinguishing Graphs via Logics with Counting (abstract)
16:20	Svetlana Popova Non-convergence in existential monadic second order logic of random graphs (abstract)

15:50-16:30 Session 9B

Transducers

Chair:

Christof Löding

Location: H 2013

15:50	Krishna S Regular Transducer Expressions for Regular Transformations (abstract)
16:00	Mikolaj Bojanczyk Regular and First Order List Functions (abstract)
16:10	Maria Emilia Descotte Resynchronizing Classes of Word Relations (abstract)

15:50-16:30 Session 9C

Games and Logic

Chair:

Lorenzo Clemente

Location: H 2032

15:50	Alexander Weinert Parity Games with Weights (abstract)
16:00	Laure Daviaud Solving mean-payoff parity games in pseudo-quasi-polynomial time. (abstract)
16:10	Thomas Zeume Introduction to Iltis: An Interactive, Web-Based System for Teaching Logic (abstract)
16:20	Roman Rabinovich Gralog, a visual tool for working with graphs, games, automata, logics (abstract)

16:40-17:20 Session 10A

Categories and Algebras

Chair:

Nikos Tzevelekos

Location: H 3010

16:40	Thorsten Wißmann Efficient and Modular Coalgebraic Partition-Refinement (abstract)
16:50	Julian Salamanca Abstract MSO languages over monads (abstract)
17:00	Henning Urbat Eilenberg Theorems for Free (abstract)
17:10	Paul Brunet Bracket Algebras: a nominal theory of interleaved scopes (abstract)

16:40-17:20 Session 10B

Logic and Automata

Chair:

Georg Zetzsche

Location: H 2013

16:40	Nicolas Mazzocchi A Pattern Logic for Automata with Outputs (abstract)
16:50	Marie Fortin It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before" (abstract)
17:00	Lorenzo Clemente Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms (abstract)
17:10	Vincent Michielini Uniformization Problem for Variants of First Order Logic over Words (abstract)

16:40-17:20 Session 10C

Automata and Games

Chair:

Nathanaël Fijalkow

Location: H 2032

16:40	Michał Skrzypczak Unambiguous languages exhaust the index hierarchy (abstract)
16:50	Denis Kuperberg Is your automaton good for playing games ? (abstract)
17:00	Simon Iosti Eventually safe languages and Good-for-Games automata (abstract)
17:10	Daniel Hausmann Permutation Games for the Weakly Aconjunctive mu-Calculus (abstract)

17:20-18:00 Session 11: Poster session

Location: H 3005

18:00-20:00Picnic (in Tiergarten)

Thursday, September 20th

View this program: with abstracts session overview talk overview

09:00-10:00 Session 12: Keynote

Chair:

Luc Segoufin

Location: H 3010

09:00

Nicole Schweikardt

Constant Delay Enumeration of Query Results (abstract)

10:00-10:30Coffee break

10:30-11:10 Session 13A

Probability and Privacy

Chair:

Laurent Doyen

Location: H 3010

10:30	Pranav Ashok Continuous-Time Markov Decisions based on Partial Exploration (abstract)
10:40	Tobias Meggendorfer Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes (abstract)
10:50	Raphaël Berthon Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes (abstract)
11:00	David Purser Bisimilarity Distances for Approximate Differential Privacy (abstract)

10:30-11:10 Session 13B

Algebra and Automata

Chair:

Jean-Eric Pin

Location: H 2013

10:30	Samuel J. V. Gool Pointlike sets for varieties determined by groups (abstract)
10:40	Chris Köcher Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid (abstract)
10:50	Thibault Godin A new hierarchy for automaton semigroups (abstract)
11:00	Ismaël Jecker A Ramsey Theorem for semigroups (abstract)

10:30-11:10 Session 13C

Vector Addition Systems

Chair:

Sylvain Schmitz

Location: H 2032

10:30	Wojciech Czerwiński The Reachability Problem for Vector Addition Systems is Not Elementary (abstract)
10:40	Jérôme Leroux Polynomial Vector Addition Systems With States (abstract)
10:50	Florian Zuleger Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS (abstract)
11:00	Georg Zetzsche Unboundedness problems for languages of vector addition systems (abstract)

11:20-12:00 Session 14: Spotlight

Chair:

Thomas Colcombet

Location: H 3010

11:20

Stéphane Gaubert

Nonarchimedean Convex Programming and Its Relation to Mean-Payoff Games (abstract)

12:00-13:30Lunch break

13:30-14:50 Session 15: Invited Session

Multi-Objective Reasoning in Probabilistic Models

Chair:

Christel Baier

Location: H 3010

13:30	Stefan Kiefer Efficient analysis of probabilistic systems that accumulate quantities (abstract)
14:10	David Parker Probabilistic Model Checking: Advances and Applications (abstract)

14:50-15:20Coffee break

15:20-16:10 Session 16A

Chair:

Laure Daviaud

Location: H 3010

15:20	Karin Quaas The Containment Problem for Unambiguous Register Automata (abstract)
15:30	Nikos Tzevelekos Polynomial-time equivalence testing for deterministic fresh-register automata (abstract)
15:40	Michaël Cadilhac Weak Cost Register Automata are Still Powerful (abstract)
15:50	Filip Mazowiecki Pumping lemmas for weighted automata (abstract)
16:00	Jakub Michaliszyn What can you expect of a weighted automaton? (abstract)

15:20-16:10 Session 16B

Logic and Games

Chair:

Dietmar Berwanger

Location: H 2013

15:20	Emanuel Martinov Reachability for Branching Concurrent Stochastic Games (abstract)
15:30	Wojtek Jamroga Towards Partial Order Reductions for Strategic Ability (abstract)
15:40	Marie Van Den Bogaard Beyond Admissibility: Rationality in Quantitative Games (abstract)
15:50	Bastien Maubert Reasoning about Knowledge and Strategies (abstract)
16:00	Aline Goeminne Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives (abstract)

15:20-16:10 Session 16C

Databases and Complexity

Chair:

Matthias Niewerth

Location: H 2032

15:20	Nils Vortmeier Reachability and Distances under Multiple Changes (abstract)
15:30	Ahmet Kara Counting Triangles under Updates in Worst-Case Optimal Time (abstract)
15:40	Jens Keppeler Answering UCQs under updates (abstract)
15:50	Pierre Ohlmann Characterization of non-associative circuits using automata, and applications (abstract)
16:00	Tomoyuki Yamakami The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata (abstract)

16:20-17:10 Session 17A

Synthesis

Chair:

Nir Piterman

Location: H 3010

16:20	Martin Zimmermann Synthesizing Optimally Resilient Controllers (abstract)
16:30	Philipp J. Meyer Strix: Explicit Reactive Synthesis Strikes Back! (abstract)
16:40	Léo Exibard Automatic Synthesis of Systems with Data (abstract)
16:50	Nathan Lhote Observation synthesis for games with imperfect information (abstract)
17:00	Laurent Doyen Graph Planning with Expected Finite Horizon (abstract)

16:20-17:10 Session 17B

Time

Chair:

Krishna S

Location: H 2013

16:20	Shibashis Guha Safe and Optimal Scheduling of Hard and Soft Tasks (abstract)
16:30	Damien Busatto-Gaston Symbolic Approximation of Weighted Timed Games (abstract)
16:40	Mahsa Shirmohammadi Costs and Rewards in Priced Timed Automata (abstract)
16:50	B Srivathsan Reachability in timed automata with diagonal constraints (abstract)
17:00	Patrick Totzke Universal Safety for Timed Petri Nets is PSPACE-complete (abstract)

16:20-17:10 Session 17C

Petri Nets and Security

Chair:

Filip Mazowiecki

Location: H 2032

16:20	Sebastian Muskalla Regular separability of WSTS (abstract)
16:30	Radosław Piórkowski Decidability in data Petri nets — a conjecture. (abstract)
16:40	Vincent Cheval DEEPSEC: Deciding Equivalence Properties in Security Protocols Theory and Practice (abstract)

17:10-18:00 Session 18: Poster session

Location: H 3005

18:00-19:00Football game (in Tiergarten)

Friday, September 21st

View this program: with abstracts session overview talk overview

09:00-10:00 Session 19: Keynote

Chair:

Mikołaj Bojanczyk

Location: H 3010

09:00

Andrei Bulatov

The Complexity of Constraints: Dichotomies and Beyond (abstract)

10:00-10:30Coffee break

10:30-12:30 Session 20: Spotlights

Chair:

James Worrell

Location: H 3010

10:30	Jeffrey Shallit Finite Automata and Additive Number Theory (abstract)
11:10	Amaury Pouly Continuous Models of Computation: Computability, Complexity, Universality (abstract)
11:50	Jan Křetínský A Journey from LTL to Your Favourite Automaton (abstract)

12:30-14:00Lunch break