Published: 9th September 2015 DOI: 10.4204/EPTCS.191 ISSN: 2075-2180 |
Fixed points play a fundamental role in several areas of computer science. They are used to justify (co)recursive definitions and associated reasoning techniques. The construction and properties of fixed points have been investigated in many different settings such as: design and implementation of programming languages, logics, verification, databases. The aim of this workshop is to provide a forum for researchers to present their results to those members of the computer science and logic communities who study or apply the theory of fixed points.
The editors thank all authors who submitted papers to FICS 2015 (successful or not), and the program committee members Ulrich Berger, Dietmar Berwanger, Filippo Bonchi, Venanzio Capretta, Krishnendu Chatterjee, Kaustuv Chaudhuri, Thomas Colcombet, Makoto Hamana, Radu Mardare, Henryk Michalewski, Andrzej Murawski, Alexandra Silva and Sam Staton for their work in selecting the 11 papers of this volume. Every submission was evaluated by three or four reviewers (we are thankful to all the external anonymous reviewers that were involved but refrain from listing them here). Some of the papers were re-reviewed after revision.
Apart from presentations of the accepted papers, we are delighted that FICS 2015 featured two invited talks: Bartek Klin on the decidability of certain infinite constraint satisfaction problems and James Worrell on the decidability of certain variants of the Skolem Problem for linear recurrence sequences. Many thanks to them for having accepted the invitation.
We could also offer the FICS'15 audience the two invited talks of the colocated annual meeting of the GI-Fachgruppe "Logik in der Informatik", given by Ulrich Schöpp and Michael Elberfeld. Thanks to them and the organizers of that meeting for making this possible.
Finally, we would like to express our deep gratitude to CSL 2015 for local organization and to EACSL and ANR ("Agence Nationale de la Recherche", France) for funding FICS 2015.
Ralph Matthes,
Matteo Mio
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 [1], 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 [4], 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.