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 abstractssession overviewtalk overview

09:30-10:30 Session 1: Tutorial
Location: H 3010
09:30
Interactions Between Proof Complexity and Finite Model Theory (part 1) (abstract)
10:30-11:00Coffee break
11:00-12:00 Session 2: Tutorial
Location: H 3010
11:00
Interactions Between Proof Complexity and Finite Model Theory (part 2) (abstract)
12:00-13:30Lunch break
13:30-15:30 Session 3: Tutorial
Location: H 3010
13:30
Principles of Probabilistic Programming (abstract)
15:30-16:00Coffee break
16:00-18:00 Session 4: Tutorial
Location: H 3010
16:00
Fine-Grained Complexity and Hardness in P (abstract)
18:00-19:00Reception (in Room H 3005)
Wednesday, September 19th

View this program: with abstractssession overviewtalk overview

09:00-10:00 Session 5: Keynote
Location: H 3010
09:00
Algebraic Invariants for Affine Programs (abstract)
10:00-10:30Coffee break
10:30-11:10 Session 6A

Automata and Languages

Location: H 3010
10:30
A unified approach to Büchi determinisation (abstract)
10:40
Algorithms for inclusion into a regular language (abstract)
10:50
Determinizing two-way automata with linear-time Turing machines (abstract)
10:30-11:10 Session 6B

Logic

Location: H 2013
10:30
An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree (abstract)
10:40
Logic and rational languages of scattered and countable series-parallel posets (abstract)
10:50
Expressing Unboudedness in MSO + nabla (abstract)
11:00
On Computing the Measures of First-Order Definable Sets of Trees (abstract)
10:30-11:10 Session 6C

Parity Games

Location: H 2032
10:30
Solving parity games in quasi-polynomial time -- a logician's approach (abstract)
10:40
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games (abstract)
10:50
Universal parity graphs and lower bounds for parity games (abstract)
11:00
Solving parity games with tangles (abstract)
11:20-12:00 Session 7: Spotlight
Location: H 3010
11:20
Symbol Elimination for Program Analysis (abstract)
12:00-13:30Lunch break
13:30-15:20 Session 8: Invited Session

Logic and Learning

Location: H 3010
13:30
The Automatic Data Scientist: Making Data Science Easier using High-level Languages, Fractional Automorphisms, and Arithmetic Circuits (abstract)
14:20
Learning Linear Temporal Properties (abstract)
14:50
Learning Models over Relational Databases (abstract)
15:20-15:50Coffee break
15:50-16:30 Session 9A

Logic and Graphs

Location: H 3010
15:50
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem (abstract)
16:00
On the First-Order Complexity of Subgraph Isomorphism (abstract)
16:10
Distinguishing Graphs via Logics with Counting (abstract)
16:20
Non-convergence in existential monadic second order logic of random graphs (abstract)
15:50-16:30 Session 9B

Transducers

Location: H 2013
15:50
Regular Transducer Expressions for Regular Transformations (abstract)
16:00
Regular and First Order List Functions (abstract)
16:10
Resynchronizing Classes of Word Relations (abstract)
15:50-16:30 Session 9C

Games and Logic

Location: H 2032
15:50
Parity Games with Weights (abstract)
16:00
Solving mean-payoff parity games in pseudo-quasi-polynomial time. (abstract)
16:10
Introduction to Iltis: An Interactive, Web-Based System for Teaching Logic (abstract)
16:20
Gralog, a visual tool for working with graphs, games, automata, logics (abstract)
16:40-17:20 Session 10A

Categories and Algebras

Location: H 3010
16:40
Efficient and Modular Coalgebraic Partition-Refinement (abstract)
16:50
Abstract MSO languages over monads (abstract)
17:00
Eilenberg Theorems for Free (abstract)
17:10
Bracket Algebras: a nominal theory of interleaved scopes (abstract)
16:40-17:20 Session 10B

Logic and Automata

Location: H 2013
16:40
A Pattern Logic for Automata with Outputs (abstract)
16:50
It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before" (abstract)
17:00
Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms (abstract)
17:10
Uniformization Problem for Variants of First Order Logic over Words (abstract)
16:40-17:20 Session 10C

Automata and Games

Location: H 2032
16:40
Unambiguous languages exhaust the index hierarchy (abstract)
16:50
Is your automaton good for playing games ? (abstract)
17:00
Eventually safe languages and Good-for-Games automata (abstract)
17:10
Permutation Games for the Weakly Aconjunctive mu-Calculus (abstract)
18:00-20:00Picnic (in Tiergarten)
Thursday, September 20th

View this program: with abstractssession overviewtalk overview

09:00-10:00 Session 12: Keynote
Location: H 3010
09:00
Constant Delay Enumeration of Query Results (abstract)
10:00-10:30Coffee break
10:30-11:10 Session 13A

Probability and Privacy

Location: H 3010
10:30
Continuous-Time Markov Decisions based on Partial Exploration (abstract)
10:40
Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes (abstract)
10:50
Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes (abstract)
11:00
Bisimilarity Distances for Approximate Differential Privacy (abstract)
10:30-11:10 Session 13B

Algebra and Automata

Location: H 2013
10:30
Pointlike sets for varieties determined by groups (abstract)
10:40
Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid (abstract)
10:50
A new hierarchy for automaton semigroups (abstract)
11:00
A Ramsey Theorem for semigroups (abstract)
10:30-11:10 Session 13C

Vector Addition Systems

Location: H 2032
10:30
The Reachability Problem for Vector Addition Systems is Not Elementary (abstract)
10:40
Polynomial Vector Addition Systems With States (abstract)
10:50
Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS (abstract)
11:00
Unboundedness problems for languages of vector addition systems (abstract)
11:20-12:00 Session 14: Spotlight
Location: H 3010
11:20
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

Location: H 3010
13:30
Efficient analysis of probabilistic systems that accumulate quantities (abstract)
14:10
Probabilistic Model Checking: Advances and Applications (abstract)
14:50-15:20Coffee break
15:20-16:10 Session 16A

Register Automata and Weighted Automata

Location: H 3010
15:20
The Containment Problem for Unambiguous Register Automata (abstract)
15:30
Polynomial-time equivalence testing for deterministic fresh-register automata (abstract)
15:40
Weak Cost Register Automata are Still Powerful (abstract)
15:50
Pumping lemmas for weighted automata (abstract)
16:00
What can you expect of a weighted automaton? (abstract)
15:20-16:10 Session 16B

Logic and Games

Location: H 2013
15:20
Reachability for Branching Concurrent Stochastic Games (abstract)
15:30
Towards Partial Order Reductions for Strategic Ability (abstract)
15:40
Beyond Admissibility: Rationality in Quantitative Games (abstract)
15:50
Reasoning about Knowledge and Strategies (abstract)
16:00
Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives (abstract)
15:20-16:10 Session 16C

Databases and Complexity

Location: H 2032
15:20
Reachability and Distances under Multiple Changes (abstract)
15:30
Counting Triangles under Updates in Worst-Case Optimal Time (abstract)
15:40
Answering UCQs under updates (abstract)
15:50
Characterization of non-associative circuits using automata, and applications (abstract)
16:00
The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata (abstract)
16:20-17:10 Session 17A

Synthesis

Location: H 3010
16:20
Synthesizing Optimally Resilient Controllers (abstract)
16:30
Strix: Explicit Reactive Synthesis Strikes Back! (abstract)
16:40
Automatic Synthesis of Systems with Data (abstract)
16:50
Observation synthesis for games with imperfect information (abstract)
17:00
Graph Planning with Expected Finite Horizon (abstract)
16:20-17:10 Session 17B

Time

Chair:
Location: H 2013
16:20
Safe and Optimal Scheduling of Hard and Soft Tasks (abstract)
16:30
Symbolic Approximation of Weighted Timed Games (abstract)
16:40
Costs and Rewards in Priced Timed Automata (abstract)
16:50
Reachability in timed automata with diagonal constraints (abstract)
17:00
Universal Safety for Timed Petri Nets is PSPACE-complete (abstract)
16:20-17:10 Session 17C

Petri Nets and Security

Location: H 2032
16:20
Regular separability of WSTS (abstract)
16:30
Decidability in data Petri nets — a conjecture. (abstract)
16:40
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 abstractssession overviewtalk overview

09:00-10:00 Session 19: Keynote
Location: H 3010
09:00
The Complexity of Constraints: Dichotomies and Beyond (abstract)
10:00-10:30Coffee break
10:30-12:30 Session 20: Spotlights
Location: H 3010
10:30
Finite Automata and Additive Number Theory (abstract)
11:10
Continuous Models of Computation: Computability, Complexity, Universality (abstract)
11:50
A Journey from LTL to Your Favourite Automaton (abstract)
12:30-14:00Lunch break