Hainry, Emmanuel Péchoux, Romain

Interpretation methods and their restrictions to polynomials have been deeply used to control the termination and complexity of first-order term rewrite systems. This paper extends interpretation methods to a pure higher order functional language. We develop a theory of higher order functions that is well-suited for the complexity analysis of this ...

Ciaffaglione, Alberto Gianantonio, Pietro Honsell, Furio Liquori, Luigi

We investigate, in the context of functional prototype-based languages , a calculus of objects which might extend themselves upon receiving a message, a possibility referred to by Cardelli as a self-inflicted operation. We present a sound type system for this calculus which guarantees that evaluating a well-typed expression will never yield a messa...

Backens, Miriam Perdrix, Simon Wang, Quanlong

The stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics. The language is sound and complete: one can transform a stabilizer ZX-diagram into another one if and only if these two diagrams represent the same quantum evolution or quantum state. We show that the stabilizer ZX-calculus can be simplified, removing...

Heath, Quentin Miller, Dale

While model checking has often been considered as a practical alternative to building formal proofs, we argue here that the theory of sequent calculus proofs can be used to provide an appealing foundation for model checking. Since the emphasis of model checking is on establishing the truth of a property in a model, we rely on additive inference rul...

Baillot, Patrick Barthe, Gilles Dal Lago, Ugo

We define a call-by-value variant of Gödel 's System T with references, and equip it with a linear dependent type and effect system, called d that can estimate the complexity of programs, as a function of the size of their inputs. We prove that the type system is intentionally sound, in the sense that it over-approximates the complexity of executin...

Jeannerod, Nicolas Treinen, Ralf

We investigate a logic of an algebra of trees including the update operation, which expresses that a tree is obtained from an input tree by replacing a particular direct subtree of the input tree, while leaving the rest unchanged. This operation improves on the expressivity of existing logics of tree algebras, in our case of feature trees. These al...

Ahrens, Benedikt Matthes, Ralph Mörtberg, Anders

The term UniMath refers both to a formal system for mathematics, as well as a computer-checked library of mathematics formalized in that system. The UniMath system is a core dependent type theory, augmented by the univalence axiom. The system is kept as small as possible in order to ease verification of it - in particular, general inductive types a...

Jeandel, Emmanuel Perdrix, Simon Vilmart, Renaud

Recent completeness results on the ZX-Calculus used a third-party language, namely the ZW-Calculus. As a consequence, these proofs are elegant, but sadly non-constructive. We address this issue in the following. To do so, we first describe a generic normal form for ZX-diagrams in any fragment that contains Clifford+T quantum mechanics. We give suff...

Monniaux, David
Published in
Acta Informatica

Automated program verification often proceeds by exhibiting inductive invariants entailing the desired properties. For numerical properties, a classical class of invariants is convex polyhedra: solution sets of system of linear (in)equalities. Forty years of research on convex polyhedral invariants have focused, on the one hand, on identifying “eas...

Fernández, Maribel Kirchner, Hélène Pinaud, Bruno

We present strategic port graph rewriting as a basis for the implementation of visual modelling tools. The goal is to facilitate the specification and programming tasks associated with the modelling of complex systems. A system is represented by an initial graph and a collection of graph rewrite rules, together with a user-defined strategy to contr...