Published: 9th September 2015|
|Invited Presentation: Topological Dynamics and Decidability of Infinite Constraint Satisfaction Bartek Klin||1|
|Invited Presentation: Reachability Problems for Continuous Linear Dynamical Systems James Worrell||2|
|Dependent Inductive and Coinductive Types are Fibrational Dialgebras Henning Basold||3|
|Equivalence of two Fixed-Point Semantics for Definitional Higher-Order Logic Programs Angelos Charalambidis, Panos Rondogiannis and Ioanna Symeonidou||18|
|Formalizing Termination Proofs under Polynomial Quasi-interpretations Naohi Eguchi||33|
|*-Continuous Kleene ω-Algebras for Energy Problems Zoltán Ésik, Uli Fahrenberg and Axel Legay||48|
|Self-Correlation and Maximum Independence in Finite Relations Dilian Gurov and Minko Markov||60|
|Iteration Algebras for UnQL Graphs and Completeness for Bisimulation Makoto Hamana||75|
|Weak Completeness of Coalgebraic Dynamic Logics Helle Hvid Hansen and Clemens Kupke||90|
|The Arity Hierarchy in the Polyadic μ-Calculus Martin Lange||105|
|Disjunctive form and the modal μ alternation hierarchy Karoliina Lehtinen||117|
|A Type-Directed Negation Elimination Etienne Lozes||132|
|Reasoning about modular datatypes with Mendler induction Paolo Torrini and Tom Schrijvers||143|
A group is called extremely amenable if every action of it on a compact space has a fixpoint. One example, shown by Pestov, is the automorphism group of the total order of rational numbers. This fact is used to establish the decidability of certain infinite constraint satisfaction problems, based on nominal sets due to Pitts.This talk is roughly based on the following paper: Bartek Klin, Eryk Kopczynski, Joanna Ochremiak, Szymon Torunczyk: Locally Finite Constraint Satisfaction Problems. LICS 2015: 475-486.
This talk is about reachability problems for continuous-time linear dynamical systems. A central decision problem in this area is the Continuous Skolem Problem , which asks whether a real-valued function satisfying an ordinary linear differential equation has a zero. This can be seen as a continuous analog of the Skolem Problem for linear recurrence sequences , which asks whether the sequence satisfying a given recurrence has a zero term. For both the discrete and continuous versions of the Skolem Problem, decidability is open.We show that the Continuous Skolem Problem lies at the heart of many natural verification questions on linear dynamical systems, such as continuous-time Markov chains and linear hybrid automata. We describe some recent work, done in collaboration with Chonev and Ouaknine [2,3], that uses results in transcendence theory and real algebraic geometry to obtain decidability for certain variants of the problem. In particular, we consider a bounded version of the Continuous Skolem Problem, corresponding to time-bounded reachability. We prove decidability of the bounded problem assuming Schanuel's conjecture, one of the main conjectures in transcendence theory. We describe some partial decidability results in the unbounded case and discuss mathematical obstacles to proving decidability of the Continuous Skolem Problem in full generality.