EPTCS 191
Proceedings Tenth International Workshop on
Fixed Points in Computer Science
Berlin, Germany, September 11-12, 2015
Edited by: Ralph Matthes and Matteo Mio
This volume contains the proceedings of the Tenth International
Workshop on Fixed Points in Computer Science (FICS 2015) which took
place on September 11th and 12th, 2015 in Berlin, Germany, as a
satellite event of the conference Computer Science Logic (CSL 2015).
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
Bartek Klin (Warsaw University)
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.
James Worrell (University of Oxford)
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.
- Paul C. Bell, Jean-Charles Delvenne, Raphaël M. Jungers, and Vincent D. Blondel. The Continuous Skolem-Pisot Problem. Theoretical Computer Science, 411(40-42):3625-3634, 2010.
- Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the decidability of the Bounded Continuous Skolem Problem. CoRR, abs/1506.00695, 2015.
- Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the decidability of the continuous infinite zeros problem. CoRR, abs/1507.03632, 2015.
- V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki. Skolem's Problem - on the border between decidability and undecidability. Technical Report 683, Turku Centre for Computer Science, 2005.