Selected Paper of the 18th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2015)

Editors: Thomas Colcombet, Andrew M. Pitts, Daniele Varacca

This special issue contains extended versions of six papers presented at FoSSaCS 2015, the 18th international conference on Foundations of Software Science and Computational Structures, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, 11-18 April 2015.

The papers collected in this special issue were invited by the guest editors, taking into account the views of the Program Committee and expert reviewers expressed during the conference paper selection process. We are grateful to the authors of all the conference papers for their excellent submissions.

The papers selected for this special issue reflect the high level of the conference and represent a wide range of topics. They underwent a new and thorough reviewing and revision process, in accordance with the usual high standards of LMCS. We thank the authors and the reviewers for all their hard work producing the contents of this issue.

Thomas Colcombet, Andrew Pitts, Daniele Varacca
FoSSaCS 2015 Guest Editors

1. The Guarded Lambda-Calculus: Programming and Reasoning with Guarded Recursion for Coinductive Types

Clouston, Ranald ; Bizjak, Aleš ; Grathwohl, Hans Bugge ; Birkedal, Lars.
We present the guarded lambda-calculus, an extension of the simply typed lambda-calculus with guarded recursive and coinductive types. The use of guarded recursive types ensures the productivity of well-typed programs. Guarded recursive types may be transformed into coinductive types by a type-former inspired by modal logic and Atkey-McBride clock quantification, allowing the typing of acausal functions. We give a call-by-name operational semantics for the calculus, and define adequate denotational semantics in the topos of trees. The adequacy proof entails that the evaluation of a program always terminates. We introduce a program logic with L\"ob induction for reasoning about the contextual equivalence of programs. We demonstrate the expressiveness of the calculus by showing the definability of solutions to Rutten's behavioural differential equations.

2. Synthesis of Strategies Using the Hoare Logic of Angelic and Demonic Nondeterminism

Mamouras, Konstantinos.
We study a propositional variant of Hoare logic that can be used for reasoning about programs that exhibit both angelic and demonic nondeterminism. We work in an uninterpreted setting, where the meaning of the atomic actions is specified axiomatically using hypotheses of a certain form. Our logical formalism is entirely compositional and it subsumes the non-compositional formalism of safety games on finite graphs. We present sound and complete Hoare-style calculi that are useful for establishing partial-correctness assertions, as well as for synthesizing implementations. The computational complexity of the Hoare theory of dual nondeterminism is investigated using operational models, and it is shown that the theory is complete for exponential time.

3. Coalgebraic trace semantics via forgetful logics

Klin, Bartek ; Rot, Jurriaan.
We use modal logic as a framework for coalgebraic trace semantics, and show the flexibility of the approach with concrete examples such as the language semantics of weighted, alternating and tree automata, and the trace semantics of generative probabilistic systems. We provide a sufficient condition under which a logical semantics coincides with the trace semantics obtained via a given determinization construction. Finally, we consider a condition that guarantees the existence of a canonical determinization procedure that is correct with respect to a given logical semantics. That procedure is closely related to Brzozowski's minimization algorithm.

4. Compositional bisimulation metric reasoning with Probabilistic Process Calculi

Gebler, Daniel ; Larsen, Kim G. ; Tini, Simone.
We study which standard operators of probabilistic process calculi allow for compositional reasoning with respect to bisimulation metric semantics. We argue that uniform continuity (generalizing the earlier proposed property of non-expansiveness) captures the essential nature of compositional reasoning and allows now also to reason compositionally about recursive processes. We characterize the distance between probabilistic processes composed by standard process algebra operators. Combining these results, we demonstrate how compositional reasoning about systems specified by continuous process algebra operators allows for metric assume-guarantee like performance validation.

5. Typing weak MSOL properties

Salvati, Sylvain ; Walukiewicz, Igor.
We consider lambda-Y-calculus as a non-interpreted functional programming language: the result of the execution of a program is its normal form that can be seen as the tree of calls to built-in operations. Weak monadic second-order logic (wMSOL) is well suited to express properties of such trees. We give a type system for ensuring that the result of the execution of a lambda-Y-program satisfies a given wMSOL property. In order to prove soundness and completeness of the system we construct a denotational semantics of lambda-Y-calculus that is capable of computing properties expressed in wMSOL.

6. Minimisation of Multiplicity Tree Automata

Kiefer, Stefan ; Marusic, Ines ; Worrell, James.
We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require a breakthrough in the complexity of polynomial identity testing by proving that the latter problem is logspace equivalent to the decision version of minimisation. The developed techniques also improve the state of the art in multiplicity word automata: we give an NC algorithm for minimising multiplicity word automata. Finally, we consider the minimal consistency problem: does there exist an automaton with $n$ states that is consistent with a given finite sample of weight-labelled words or trees? We show that this decision problem is complete for the existential theory of the rationals, both for words and for trees of a fixed alphabet rank.