Dubois C.,ENSIIE CEDRIC |
Pessaux F.,ENSTA ParisTech
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2016
FoCaLiZe is a development environment allowing the writing of specifications, implementations and correctness proofs. It generates both OCaml (executable) and Coq code (for verification needs). This paper extends the language and the compiler to handle termination proofs relying on well-founded relations or measures. We propose an approach where the user’s burden is lightened as much as possible, leaving glue code to the compiler. Proofs are written using the declarative proof language provided by FoCaLiZe, and the automatic theorem prover Zenon. When compiling to Coq we rely on the Coq construct Function. © Springer International Publishing Switzerland 2016.
Burel G.,ENSIIE Cedric |
Cruanes S.,French Institute for Research in Computer Science and Automation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2013
Automated theorem provers for first-order logic with equality have become very powerful and useful, thanks to both advanced calculi - such as superposition and its refinements - and mature implementation techniques. Nevertheless, dealing with some axiomatic theories remains a challenge because it gives rise to a search space explosion. Most attempts to deal with this problem have focused on specific theories, like AC (associative commutative symbols) or ACU (AC with neutral element). Even detecting the presence of a theory in a problem is generally solved in an ad-hoc fashion. We present here a generic way of describing and recognizing axiomatic theories in clausal form first-order logic with equality. Subsequently, we show some use cases for it, including a redundancy criterion that can be applied to some equational theories, extending some work that has been done by Avenhaus, Hillenbrand and Löchner. © 2013 Springer-Verlag.
Burel G.,ENSIIE Cedric
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2014
Deduction modulo is a framework in which theories are integrated into proof systems such as natural deduction or sequent calculus by presenting them using rewriting rules. When only terms are rewritten, cut admissibility in those systems is equivalent to the confluence of the rewriting system, as shown by Dowek, RTA 2003, LNCS 2706. This is no longer true when considering rewriting rules involving propositions. In this paper, we show that, in the same way that it is possible to recover confluence using Knuth-Bendix completion, one can regain cut admissibility in the general case using standard saturation techniques. This work relies on a view of proposition rewriting rules as oriented clauses, like term rewriting rules can be seen as oriented equations. This also leads us to introduce an extension of deduction modulo with conditional term rewriting rules. © 2014 Springer International Publishing Switzerland.
Assaf A.,French Institute for Research in Computer Science and Automation |
Assaf A.,Ecole Polytechnique - Palaiseau |
Burel G.,ENSIIE Cedric
Electronic Proceedings in Theoretical Computer Science, EPTCS | Year: 2015
Dedukti is a logical framework based on the λΠ-calculus modulo rewriting, which extends the λΠ-calculus with rewrite rules. In this paper, we show how to translate the proofs of a family of HOL proof assistants to Dedukti. The translation preserves binding, typing, and reduction. We implemented this translation in an automated tool and used it to successfully translate the OpenTheory standard library. © A. Assaf and G. Burel This work is licensed under the Creative Commons Attribution License.
Yaman H.,Bilkent University |
Elloumi S.,ENSIIE CEDRIC
Computers and Operations Research | Year: 2012
We consider two problems that arise in designing two-level star networks taking into account service quality considerations. Given a set of nodes with pairwise traffic demand and a central hub, we select p hubs and connect them to the central hub with direct links and then we connect each nonhub node to a hub. This results in a star/star network. In the first problem, called the Star p-hub Center Problem, we would like to minimize the length of the longest path in the resulting network. In the second problem, Star p-hub Median Problem with Bounded Path Lengths, the aim is to minimize the total routing cost subject to upper bound constraints on the path lengths. We propose formulations for these problems and report the outcomes of a computational study where we compare the performances of our formulations. © 2012 Elsevier Ltd. All rights reserved.