HIGHLIGHTS 2018: HIGHLIGHTS OF LOGIC, GAMES AND AUTOMATA
PROGRAM

Days: Tuesday, September 18th Wednesday, September 19th Thursday, September 20th Friday, September 21st

Tuesday, September 18th

View this program: with abstracts

09:30-10:30 Session 1: Tutorial
Chair:
Oleg Verbitsky
09:30
Christoph Berkholz
Interactions Between Proof Complexity and Finite Model Theory (part 1) (abstract)
10:30-11:00Coffee break
11:00-12:00 Session 2: Tutorial
Chair:
Oleg Verbitsky
11:00
Christoph Berkholz
Interactions Between Proof Complexity and Finite Model Theory (part 2) (abstract)
12:00-13:30Lunch break
13:30-15:30 Session 3: Tutorial
Chair:
Richard Mayr
13:30
Joost-Pieter Katoen
Principles of Probabilistic Programming (abstract)
15:30-16:00Coffee break
16:00-18:00 Session 4: Tutorial
Chair:
Thomas Zeume
16:00
Amir Abboud
Fine-Grained Complexity and Hardness in P (abstract)
18:00-19:00Reception (in Room H 3005)
Wednesday, September 19th

View this program: with abstracts

09:00-10:00 Session 5: Keynote
Chair:
Erich Grädel
09:00
James Worrell
Algebraic Invariants for Affine Programs (abstract)
10:00-10:30Coffee break
10:30-11:10 Session 6A

Automata and Languages

Chair:
Martin Zimmermann
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
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
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
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
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
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
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
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
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
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
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)
18:00-20:00Picnic (in Tiergarten)
Thursday, September 20th

View this program: with abstracts

09:00-10:00 Session 12: Keynote
Chair:
Luc Segoufin
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
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
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
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
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
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

Register Automata and Weighted Automata

Chair:
Laure Daviaud
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
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
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
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
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
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)
18:00-19:00Football game (in Tiergarten)
Friday, September 21st

View this program: with abstracts

09:00-10:00 Session 19: Keynote
Chair:
Mikołaj Bojanczyk
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
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