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
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.
- registration is obligatory
- the registration fee is 50 euros
- registration includes lunch and coffee break(s) on Friday and Saturday
- no late registration fee applies, but early registration is appreciated
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:
- fixed points in algebra and coalgebra
- fixed points in formal languages and automata
- fixed points in game theory
- fixed points in programming language semantics
- fixed points in the mu-calculus and modal logics
- fixed points in process algebras and process calculi
- fixed points in functional programming and type theory
- fixed points in relation to dataflow and circuits
- fixed points in logic programming and theorem proving
- fixed points in finite model theory, descriptive complexity theory,
- fixed points in category theory for logic in computer science
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.
- 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.
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
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
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
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.
11 contributed papers were accepted for presentation at the workshop, here is the full list and here is the list with abstracts.
- Tuesday, June 16: Abstract submission (late abstract submission tolerated until Wednesday June 24, 11:30 a.m. Paris time)
- Tuesday, June 23: Paper submission (late paper submission tolerated until Friday June 26, noon Paris time)
- Monday, July 27: Notification (done by 6 p.m. Paris time)
- Monday, August 24: Final version
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:
- Peter Dybjer (Chalmers University of Technology)
- Anna Ingolfsdottir (Reykjavik University)
- Ralph Matthes, chair (IRIT, Toulouse)
- Dale Miller (INRIA / Ecole Polytechnique, Palaiseau)
- Damian Niwinski (University of Warsaw)
- Luigi Santocanale (LIF, Université Aix-Marseille I)
- Alex Simpson (University of Ljubljana)
- Tarmo Uustalu (Institute of Cybernetics, Tallinn)
- Igor Walukiewicz (LaBRI, Bordeaux)
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