Fixed Points in Computer Science 2015 (September 11-12, 2015)

The 10th International Workshop on Fixed Points in Computer Science will take place in Berlin on 11 and 12 September 2015 as a satellite of the International Conference CSL 2015 (Computer Science Logic).

News: Slides of invited talks available, see below for invited speakers

practical matters

Registration is handled by the CSL conference organizers, please see the dedicated web page there. The basic facts are (please refer to the mentioned URL for the formal data): Of course, we understand that participants normally register when the programme is known, but notification has been only on July 27, and the list of accepted contributed talks has been available below since July 28.

general description

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. Topics include, but are not restricted to:

programme committee

invited speakers

Bartek Klin, Warsaw University
Topological Dynamics and Decidability of Infinite Constraint Satisfaction (PDF of ~3MB)
preliminary abstract (final abstract in EPTCS proceedings): 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. I will show how to use this fact to establish the decidability of certain infinite constraint satisfaction problems, based on nominal sets due to Pitts. (This is joint work with E. Kopczynski, J. Ochremiak and S. Torunczyk.)
James Worrell, University of Oxford
Reachability Problems for Continuous Linear Dynamical Systems (PDF of <1MB)
preliminary abstract (final abstract in EPTCS proceedings): This talk focusses on reachability problems for solutions of linear differential equations. For example we consider the problem of whether it is possible to escape a particular location of a linear hybrid automaton given initial values of the continuous variables. We also consider the problem of whether a given set of probability distributions is reachable during the evolution of continuous-time Markov chain. A canonical such decision problem 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. We describe some recent work, done in collaboration with Chonev and Ouaknine, that uses results in transcendence theory and Diophantine approximation 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, a central conjecture 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.

programme

We will mutualize the invited talks on Friday with the annual meeting of the GI-Fachgruppe "Logik in der Informatik", in short "the GI meeting". Invited speakers have 55 minutes incl. discussion (allowing for room change because of the mutualization of invited speakers), for contributed talks, 25 minutes are allotted.

The abstracts of the invited talks and all papers are found in the EPTCS volume 191 (DOI: 10.4204/EPTCS.191) that was published on September 9, 2015. The entire proceedings volume in one PDF is mostly intended for printing (attention: letter format, users of Acrobat Reader in desire of A4 printing might want to use Page Scaling: None + Auto Rotate and Center).

(incorporating a switch of 2 slots made on August 28 agreed to by those concerned)

=================================================
The venue: main university building of Technical University of Berlin, officially
Hauptgebäude der Technischen Universität Berlin
Straße des 17. Juni 135
10623 Berlin
Germany

Friday, Sept 11, 2015

08:00 - Registration in room H3005

08:50 Opening in room H2053

09:00 FICS'15 invited talk 1 - jointly with GI meeting: Bartek Klin. "Topological Dynamics and Decidability of Infinite Constraint Satisfaction"
10:00 Helle Hvid Hansen and Clemens Kupke. "Weak Completeness of Coalgebraic Dynamic Logics"

10:30 Coffee break (all coffee breaks in H3005)

11:00 GI meeting invited talk 1 in room H2032: Ulrich Schöpp. "On Interaction Semantics as an Approach to Organising Low-Level Programs"
12:00 (continuation in room H2053) Henning Basold. "Dependent Inductive and Coinductive Types are Fibrational Dialgebras"

12:30 Lunch break (off site)

14:00 GI meeting invited talk 2 in room H2032: Michael Elberfeld. "Expressivity of Monadic Second-Order Logic on Structured Graphs"
15:00 (continuation in room H2053) Makoto Hamana. "Iteration Algebras for UnQL Graphs and Completeness for Bisimulation"

15:30 Coffee break

FICS-only session in room H2053

16:00 Paolo Torrini and Tom Schrijvers. "Reasoning about modular data-types with Mendler induction"
16:30 Angelos Charalambidis, Panos Rondogiannis and Ioanna Symeonidou. "Equivalence of two Fixed-Point Semantics for Definitional Higher-Order Logic Programs"
17:00 Naohi Eguchi. "Formalizing Termination Proofs under Polynomial Quasi-interpretations"
17:30 Dilian Gurov and Minko Markov. "Self-Correlation and Maximum Independence in Finite Relations"

19:30 Dinner (to be confirmed, not included in the registration fee)

--------------

Saturday, Sept 12, 2015: room H2053 for the scientific part

09:00 FICS'15 invited talk 2: James Worrell. "Reachability Problems for Continuous Linear Dynamical Systems"
10:00 Zoltan Esik, Uli Fahrenberg and Axel Legay. "*-Continuous Kleene omega-Algebras for Energy Problems"

10:30 Coffee break

11:00 Karoliina Lehtinen. "Disjunctive form and the modal mu alternation hierarchy"
11:30 Martin Lange. "The Arity Hierarchy in the Polyadic mu-Calculus"
12:00 Etienne Lozes. "A Type-Directed Negation Elimination"

12:30 Lunch break (on site: room H3005)

14:00 End of FICS'15
===========================================

submission

The selection of contributed talks will be based on extended abstracts/short papers describing original results in sufficient detail to constitute a publication. Submission is exclusively via EasyChair on the dedicated site (closed for submission).

Accepted papers will be published through the open-access venue EPTCS. Submissions should be composed using LaTeX and, preferably, using the EPTCS style.

Typical submissions would be 8 pages long but submissions in the range [6,15] pages will be considered acceptable. If you have good reasons to go below the lower bound, then please contact the PC chairs before submission.

Submissions (co-)authored by program comittee members other than the co-chairs are allowed and will be assessed in the EasyChair system that is perfectly capable of hiding information to program committee members with a conflict of interest.

important dates

accepted talks

11 contributed papers were accepted for presentation at the workshop, here is the full list and here is the list with abstracts.

journal publication

If the number and quality of submissions justifies it, a subsequent special issue of a journal will be prepared with extended versions of selected papers. A special issue of FICS 2013 is in preparation and will appear in Fundamenta Informaticae.

steering committee of the FICS workshop series

unchanged since FICS 2013 (but the affiliation of Alex Simpson has changed), in detail:

FICS history

Please see the history on the website of FICS 2013

Page maintained by:

Ralph Matthes
https://www.irit.fr/~Ralph.Matthes/

Last modified (date in French): lun. sept. 14 22:21:06 CEST 2015