Author: "Department of Formal Methods (LORIA - FM)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Department of Formal Methods (LORIA - FM)"' showing total 1,682 results

Start Over Author "Department of Formal Methods (LORIA - FM)"

1,682 results on '"Department of Formal Methods (LORIA - FM)"'

1. A Static Checker for Reference Tracking Systems via Laplace Transform and Transfer Functions

Author: Cheng, Zheng, Méry, Dominique, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), TELECOM Nancy, Université de Lorraine (UL), and ANR-17-CE25-0005,DISCONT,Intégration correcte de modèles discrets et continus(2017)
Subjects: Laplace transform, formal method, [INFO]Computer Science [cs], ACM: D.: Software, verification, ACM: F.: Theory of Computation, control theory, ACM: G.: Mathematics of Computing
Abstract: We propose a static checker, based on the Laplace transform, for checking reference tracking system designs against their performance and safety requirements. It aims to filter out designs that have obvious requirement violations. This is to prevent users from performing more expensive evaluation tasks (e.g., simulation, model checking, or theorem proving) until those violations are reviewed or fixed. In the process, our checker depends on domain knowledge of the Laplace transform to represent each design into a mathematical model, namely the transfer function. Then, it derives time-domain metrics and interprets them as first-order formulas over real numbers. By doing so, we can formulate a proof obligation for checking requirement violations of a design in the Z3 SMT solver. We evaluated our approach on 10 designs from the literature and textbooks to demonstrate its practical usage and identify its limitations.
Published: 2023

2. Expiring opacity problems in parametric timed automata

Author: Lefaucheux, Engel, André, Étienne, Marinho, Dylan, Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019), and ANR-22-CE48-0012,BisoUS,Better Synthesis for Underspecified Quantitative Systems(2022)
Subjects: timed opacity, [INFO]Computer Science [cs], security, Timed automata
Abstract: Information leakage can have dramatic consequences on the security of real-time systems. Timing leaks occur when an attacker is able to infer private behavior depending on timing information. In this work, we propose a definition of expiring timed opacity w.r.t. execution time, where a system is opaque whenever the attacker is unable to deduce the reachability of some private state solely based on the execution time; in addition, the secrecy is violated only when the private state was visited "recently", i. e., within a given time bound (or expiration date) prior to system completion. This has an interesting parallel with concrete applications, notably cache deducibility: it may be useless for the attacker to know the cache content too late after its observance. We study here expiring timed opacity problems in timed automata. We consider the set of time bounds (or expiration dates) for which a system is opaque and show when they can be effectively computed for timed automata. We then study the decidability of several parameterized problems, when not only the bounds, but also some internal timing constants become timing parameters of unknown constant values.
Published: 2023

3. Towards an Automatic Proof of the Bakery Algorithm

Author: Goel, Aman, Merz, Stephan, Sakallah, Karem A., Amazon Web Services [Seattle] (AWS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), University of Michigan [Ann Arbor], University of Michigan System, and Marieke Huisman and Ant{\'o}nio Ravara
Subjects: mutual exclusion, inductive invariant, parameterized verification, [INFO]Computer Science [cs]
Abstract: International audience; The Bakery algorithm is a landmark algorithm for ensuring mutual exclusion among N processes that communicate via shared variables. Starting from existing TLA+ specifications, we use the recently-developed IC3PO parameterized model checker to automatically compute inductive invariants for two versions of the algorithm. We compare the machine-generated invariants with human-written invariants that were used in an interactive correctness proof checked by the TLA+ Proof System. Our experience suggests that automated invariant inference is becoming a viable alternative to labor-intensive human-written proofs.
Published: 2023

4. Récurrence nœthérienne pour le raisonnement de premier ordre

Author: Stratulat, Sorin, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
Abstract: National audience; La récurrence nœthérienne est un des principes les plus généraux de raisonnement formel. Dans le cadre du raisonnement de premier ordre, nous présentons une classification de ses instances pouvant être partagées en instances basées sur des termes et des formules. Nous donnons un aperçu du raisonnement par récurrence nœthérienne basée sur des termes et sur des formules, puis nous établissons des relations entre eux. Enfin, nous présentons une méthodologie pour la certification du raisonnement basé sur des formules à l’aide de l’assistant de preuve Coq.
Published: 2022

5. Mechanical certification of FOLID cyclic proofs

Author: Sorin Stratulat, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: E-Cyclist, Artificial Intelligence, Applied Mathematics, automated reasoning cyclic induction first-order logic with inductive definitions proof certification Coq E-Cyclist, proof certification, Coq, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], first-order logic with inductive definitions, cyclic induction, automated reasoning
Abstract: International audience; Cyclic induction is a powerful reasoning technique that can soundly stop the proof development and make the proof experience successful. In the setting of first-order logic with inductive definitions (FOLID), cyclic proofs can be built automatically by the Cyclist prover but their implementations are error-prone and the human validation may be tedious. On the other hand, cyclic induction is not yet integrated in certifying proof environments that support first-order logic and inductive definitions, as Isabelle and Coq.
Published: 2023

6. Formal domain-driven system development in Event-B: Application to interactive critical systems

Author: Ismail Mendil, Yamine Aït-Ameur, Neeraj Kumar Singh, Guillaume Dupont, Dominique Méry, Philippe Palanque, Assistance à la Certification d’Applications DIstribuées et Embarquées (IRIT-ACADIE), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), TELECOM Nancy, Université de Lorraine (UL), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Interactive Critical Systems (IRIT-ICS), ANR-16-CE25-0007,FORMEDICIS,Méthodes formelles pour le développement et l'ingénierie de systèmes interactifs critiques(2016), and ANR-19-CE25-0010,EBRP-EventB-Rodin-Plus,Enrichissement de EventB et de RODIN : EventB-Rodin-Plus(2019)
Subjects: TCAS, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Hardware and Architecture, Ontology, Refinement and proofs, Formal methods, Domain knowledge, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Event-B, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], Interactive system, Software
Abstract: International audience; The design of complex and/or critical systems requires handling the environment constraints in which these systems evolve. Formal methods allow system developers to design models of such systems. They provide constructs for modelling components and views of these systems. However, these formal methods do not include built-in constructs for modelling the environment, and more broadly, domain knowledge associated with system models. Although ontologies have demonstrated their efficiency in modelling domain-specific features, they are not available as built-in constructs in formal methods.This paper shows how formal ontologies can be used to model domain-specific knowledge, as well as how system models may refer to these ontologies through annotation. We rely on the Event-B refinement and proof state-based method, and the associated theories, to define a framework in which domain-specific knowledge ontologies are formalised as Event-B theories defining data types used to type Event-B system design models. Finally, this framework is deployed for the specific case of interactive critical systems. To illustrate the proposed approach, a case study of the Traffic Collision Avoidance System (TCAS) is developed.
Published: 2023

7. A Computational Approach to Complete Exact and Approximate Conservation Laws of Chemical Reaction Networks

Author: Desoeuvres, Aurélien, Iosif, Alexandru, Lüders, Christoph, Radulescu, Ovidiu, Rahkooy, Hamid, Seiß, Matthias, Sturm, Thomas, Laboratory of Pathogen Host Interactions [Montpellier] (LPHI), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), IE University [Campus Madrid], Universität Bonn = University of Bonn, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, University of Kassel, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), and Sturm, Thomas
Subjects: [SDV] Life Sciences [q-bio], 37N25, 92C45, 14-04, 34C14, 13P10, Molecular Networks (q-bio.MN), FOS: Biological sciences, [SDV]Life Sciences [q-bio], [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], FOS: Mathematics, [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], Quantitative Biology - Molecular Networks, Dynamical Systems (math.DS), Mathematics - Dynamical Systems
Abstract: We consider chemical reaction networks (CRN) with monomial reaction rates. For these models, we introduce and discuss the concepts of exact and approximate conservation laws, that are first integrals of the full and truncated sets of ODEs. For fast-slow CRNs, truncated ODEs describe the fast dynamics. We define compatibility classes as subsets of the species concentration space, obtained by equating the conservation laws to constants. A set of conservation laws is complete when the corresponding compatibility classes contain a finite number of steady states (quasi-steady states for approximate conservation laws of fast-slow systems). Complete sets of conservation laws can be used for reducing CRNs by variable pooling. We provide algorithmic methods for computing linear, monomial and polynomial conservation laws of CRNs and for testing their completeness. The resulting conservation laws and their completeness are are either independent or dependent on the parameters. In the latter case, we provide parametric case distinctions. In particular, we propose a new method to compute polynomial conservation laws by comprehensive Gr\"obner systems and syzygies. Keywords: First integrals, chemical reaction networks, polynomial conservation laws, syzygies, comprehensive Gr\"obner systems.
Published: 2022

8. Zone extrapolations in parametric timed automata

Author: Johan Arcile, Étienne André, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Klaus Havelund, Jyo Deshmukh, Ivan Perez, and ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019)
Subjects: FOS: Computer and information sciences, liveness, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Computer Science - Logic in Computer Science, parameter synthesis, Formal Languages and Automata Theory (cs.FL), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], parametric timed automata, IMITATOR, Computer Science - Formal Languages and Automata Theory, abstraction, Logic in Computer Science (cs.LO), reachability
Abstract: Timed automata (TAs) are an efficient formalism to model and verify systems with hard timing constraints, and concurrency. While TAs assume exact timing constants with infinite precision, parametric TAs (PTAs) leverage this limitation and increase their expressiveness, at the cost of undecidability. A practical explanation for the efficiency of TAs is zone extrapolation, where clock valuations beyond a given constant are considered equivalent. This concept cannot be easily extended to PTAs, due to the fact that parameters can be unbounded. In this work, we propose several definitions of extrapolation for PTAs based on the M-extrapolation, and we study their correctness. Our experiments show an overall decrease of the computation time and, most importantly, allow termination of some previously unsolvable benchmarks., This is the author (and extended) version of the manuscript of the same name published in the proceedings of the 14th NASA Formal Methods Symposium (NFM 2022). This work is partially supported by the ANR-NRF French-Singaporean research program ProMiS (ANR-19-CE25-0015)
Published: 2022

9. strategFTO: Untimed control for timed opacity

Author: André, Étienne, Bolat, Shapagat, Lefaucheux, Engel, Marinho, Dylan, Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), This work is partially supported by the ANR-NRF French-Singaporean research program ProMiS (ANR-19-CE25-0015 / 2019 ANR NRF 0092) and the ANR research program BisoUS., Cyrille Artho, Peter Ölveczky, ANR research program BisoUS, and ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science - Cryptography and Security, Formal Languages and Automata Theory (cs.FL), opacity, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Computer Science - Formal Languages and Automata Theory, security, timing leak, Logic in Computer Science (cs.LO), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], timed automata, IMITATOR, control, Cryptography and Security (cs.CR)
Abstract: We introduce a prototype tool strategFTO addressing the verification of a security property in critical software. We consider a recent definition of timed opacity where an attacker aims to deduce some secret while having access only to the total execution time. The system, here modeled by timed automata, is deemed opaque if for any execution time, there are either no corresponding runs, or both public and private corresponding runs. We focus on the untimed control problem: exhibiting a controller, i.e., a set of allowed actions, such that the system restricted to those actions is fully timed-opaque. We first show that this problem is not more complex than the full timed opacity problem, and then we propose an algorithm, implemented and evaluated in practice., This work is partially supported by the ANR-NRF French-Singaporean research program ProMiS (ANR-19-CE25-0015 / 2019 ANR NRF 0092) and the ANR research program BisoUS. Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several universities as well as other organizations
Published: 2022

10. Specification and Verification with the TLA+ Trifecta: TLC, Apalache, and TLAPS

Author: Konnov, Igor, Kuppe, Markus, Merz, Stephan, Informal systems [Vienna], Microsoft Research, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and ANR-21-CE25-0015,ICSPA,Assistants de preuve basés sur la théorie des ensembles interopérables et sûrs(2021)
Subjects: FOS: Computer and information sciences, Model checking, Computer Science - Logic in Computer Science, TLA+, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], TLA +, Specification, Theorem proving, Logic in Computer Science (cs.LO)
Abstract: International audience; Using an algorithm due to Safra for distributed termination detection as a running example, we present the main tools for verifying specifications written in TLA+. Examining their complementary strengths and weaknesses, we suggest a workflow that supports different types of analysis and that can be adapted to the desired degree of confidence.
Published: 2022

11. A Comprehensive Framework for Saturation Theorem Proving

Author: Waldmann, Uwe, Tourret, Sophie, Robillard, Simon, Blanchette, Jasmin, Peltier, Nicolas, Sofronie-Stokkermans, Viorica, Theoretical Computer Science, Network Institute, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft, Département Automatique, Productique et Informatique (IMT Atlantique - DAPI), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Vrije Universiteit Amsterdam [Amsterdam] (VU), Proof-oriented development of computer-based systems (MOSEL), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Peltier, Nicolas, Sofronie-Stokkermans, Viorica, Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Montpellier (UM), and IMT Atlantique (IMT Atlantique)
Subjects: Computer science, Prover architectures, 02 engineering and technology, Gas meter prover, Mathematical proof, Article, Image (mathematics), Automated theorem proving Saturation Resolution calculus Superposition calculus Redundancy Prover architectures, Redundancy, Artificial Intelligence, Completeness (order theory), 0202 electrical engineering, electronic engineering, information engineering, Calculus, Redundancy (engineering), Automated theorem proving, Superposition calculus, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, Resolution (logic), Saturation, Resolution calculus, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Cover (topology), Computational Theory and Mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 020201 artificial intelligence & image processing, Software
Abstract: A crucial operation of saturation theorem provers is deletion of subsumed formulas. Designers of proof calculi, however, usually discuss this only informally, and the rare formal expositions tend to be clumsy. This is because the equivalence of dynamic and static refutational completeness holds only for derivations where all deleted formulas are redundant, but the standard notion of redundancy is too weak: A clause C does not make an instance $$C\sigma $$ C σ redundant. We present a framework for formal refutational completeness proofs of abstract provers that implement saturation calculi, such as ordered resolution and superposition. The framework modularly extends redundancy criteria derived via a familiar ground-to-nonground lifting. It allows us to extend redundancy criteria so that they cover subsumption, and also to model entire prover architectures so that the static refutational completeness of a calculus immediately implies the dynamic refutational completeness of a prover implementing the calculus within, for instance, an Otter or DISCOUNT loop. Our framework is mechanized in Isabelle/HOL.
Published: 2022

12. Making Higher-Order Superposition Work

Author: Vukmirović, P., Bentkamp, A., Blanchette, J., Cruanes, S., Nummelin, V., Tourret, S., Platzer, André, Sutcliffe, Geoff, Vrije Universiteit Amsterdam [Amsterdam] (VU), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Aesthetic Integration, Theoretical Computer Science, Network Institute, Computer Science, Computer Systems Section - Vrije Universiteit Amsterdam, Max-Planck-Gesellschaft, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Platzer, André, Sutcliffe, Geoff, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), and Max-Planck-Gesellschaft-Max-Planck-Gesellschaft
Subjects: Higher-order theorem proving, Theoretical computer science, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Branching (linguistics), Competition (economics), Superposition principle, Artificial Intelligence, Order (exchange), 0202 electrical engineering, electronic engineering, information engineering, Heuristics, SDG 7 - Affordable and Clean Energy, 0101 mathematics, Rule of inference, Superposition, 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, Extension (predicate logic), Division (mathematics), Automated theorem proving, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Zipperposition, Software
Abstract: This archive contains the raw evaluation results and scripts associated with the experiments described in the article "Making Higher-Order Superposition Work" by Vukmirović, Bentkamp, Blanchette, Cruanes, Nummelin and Tourret available at: https://matryoshka-project.github.io/pubs/mhosw_article.pdf The problems we used for the evaluation are in problems/ subdirectory, divided in categories sh and tptp as in the article. In the results/ directory there are two subdirectories, sh and tptp, one for each benchmark category. Both subdirectories contain files named fD.csv where D is a number from 1 to 10. The files contain experiment results for the figure labelled with the number D, and the benchmark category corresponding to the parent directory. In the result files, the columns give the results of the experiment run for a given prover configuration (e.g., CPU time, reported status, memory usage, etc.). Each row corresponds to one problem file, whose name is given in the "prob_name" column. The "i_solver" column corresponds to a prover, whereas the "i_configuration" column corresponds to a configuration, where i is a natural number identifying a combination of prover and configuration. Files ending with "summary.csv" contain concise summaries of evaluation runs for a corresponding results file. Columns of these files are of the form "{solver}_{configuration}", and rows contain different statistics described in the "summary" column. The names of the solvers and configurations used in result files are self-explanatory (for DCS, DCI and IC configurations presence of av in the name of the configuration denotes that Avatar is enabled). In some cases, for uniformity, configurations are used in multiple figures. We used the following versions of higher-order provers: CVC4 1.9 ([git cascJ10 db26022c]), Leo-III 1.5.6, Satallax 3.5, Vampire 4.5.1 (commit 68d3e7314), E 2.7 (603992156b943171002cacca72aa3f2d0a211ee3). The "zipperposition/" directory contains the scripts that can be used to run the provided Zipperposition binary (compiled for Linux) on a given problem using a given configuration. To run Zipperposition on a single problem using some configuration, use the scripts with the name "run_*", where * stands for the configuration used in the evaluation. The configuration names match those used in the result files. Except for "run_coop" and "run_uncoop", scripts accept three arguments: 1) path to the problem 2) CPU timeout 3) path to the temporary directory for files used to communicate with Ehoh. "run_coop" and "run_uncoop" expect only the first two arguments For example, to run problem with the path ~/problem.p using configuration which enables PEHO priority function for up to 15 seconds execute ./run_prio_peho ~/problem.p 15 /tmp Working installation of Python 3 and bash is required. Source code for Zipperposition can be obtained from the wip-merge-hlbe branch of Zipperposition git repository: git@github.com:sneeuwballen/zipperposition.git. The binary stored under scripts/ directory corresponds to compiled sources tagged with commit hash 8d205ecf8869c76dcfdf0c1faa98b002226780a1. Compilation instructions are as in README.md file contained in the git repository. As noted in footnote 2, three tables have been evaluated using a faulty version of Ehoh prover. Reevaluation is being performed, and it is expected that the evaluation results will stay mostly the same, up to the noise in the evaluation environment. "eprover-ho" binary provided in this archive is the corrected version of the one used to evaluate tables 7, 8 and 9.
Published: 2022

13. Consolidation des solveurs SMT pour les assistants de preuve : preuves, simplification des quantificateurs, planification de stratégies

Author: Schurr, Hans-Jörg, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), INRIA, Université de Lorraine, Stephan Merz, Pascal Fontaine, and European Project: 713999,H2020,Matryoshka(2017)
Subjects: Raisonnement automatique, Computer Sciences, SMT, Verification, Prouveur interactif, Vérification, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Automated reasoning
Abstract: This thesis presents three contributions that have the same underlying motivation: to improve the utility of SMT solvers as backends for proof assistants. SMT solvers are automated theorem provers that combine propositional reasoning with theories. Proof assistants are tools that empower users to write formally checked proofs. To help the user,proof assistants can provide automation by integrating with automated theorem provers. Proof assistants typically accept only proofs that are constructed in the trusted kernel of the assistant. The first contribution addresses the reconstruction of SMT proofs in a proof assistant. We present the Alethe proof format for SMT solvers. It improves and unifies previous work on proof generation from SMT solvers. The vast majority of these improvements were informed by the experience provided by a concrete effort of reconstructing Alethe proofs in the proof assistant Isabelle/HOL.SMT problems generated by proof assistants usually really heavily on quantifiers. Since SMT solvers excel on quantifier free problems, they use quantifier instantation to generate quantifier free formulas. The second contribution improves quantifier instantiation. It is aunification-based method that augments the problem with shallow quantified formulas obtained from assertions with nested quantifiers. These new formulas help unlocking the regular instantiation techniques, but parsimony is necessary since they might also be misguiding. The method allows the solver to prove more formulas, faster. The heuristics of an SMT solvers can be parameterized. A specific parameterization of the entire solver is called a strategy, and the best strategy usually differs from problem to problem. The third contributionis a toolbox to work with strategy schedules. A key component of the toolbox is a tool that uses integer programming to generate strategy schedules. Beyond this tool, the toolbox also contains tools for simulating and analyzing schedules. We used the toolbox to select strategies that solve many problems generated by Isabelle/HOL.; Cette thèse présente trois contributions qui ont pour objectif d'améliorer l'utilité des solveurs SMT comme backends pour les assistants de preuve. Les solveurs SMT sont des outils de démonstration automatique de théorèmes qui intègrent le raisonnement propositionnel avec des théories. Un assistant de preuve est un logiciel qui permet aux utilisateurs d'écrire des preuves vérifiées formellement. Pour aider l'utilisateur, les assistants de preuve proposent certaines automatisations utilisant des outils de démonstration automatiques. Les assistants de preuve n'acceptent généralement que les preuves qui utilisent le formalisme proposé par l'assistant. La première contribution traite de la reconstruction de preuves SMT dans un assistant de preuve. Nous présentons le format de preuve Alethe pour les solveurs SMT. Il améliore et unifie les travaux antérieurs sur la génération de preuves à partir de solveurs SMT. La grande majorité de ces améliorations a été inspirée par l'expérience acquise par un travail substantiel visant à la reconstruction de preuves Alethe dans l'assistant de preuve Isabelle/HOL. Les problèmes SMT générés par les assistants de preuve dépendent largement des quantificateurs. Puisque les solveurs SMT sont particulièrement adaptés aux problèmes sans quantificateurs, ils utilisent l'instantation des quantificateurs pour générer des formules sans quantificateurs. La deuxième contribution améliore l'instanciation des quantificateurs. Il s'agit d'une méthode basée sur l'unification qui enrichie le problème avec des formules quantifiées superficielles obtenues à partir d'assertions avec des quantificateurs imbriqués. Ces nouvelles formules aident à débloquer l'utilisation des techniques d'instanciation classiques, mais elles doivent être utilisées avec parcimonie car elles peuvent aussi être mal interprétées. Cette méthode permet au solveur de prouver plus de formules, plus rapidement. L'utilisation d'un solveur SMT est fortement paramétrable. Un paramétrage spécifique est appelé une stratégie, et la meilleure stratégie diffère généralement d'un problème à l'autre. La troisième contribution est une panoplie d'outils destinée à faciliter l'utilisation et le choix de ces stratégies. Un des outils majeurs propose d'utiliser l'optimisation linéaire en nombres entiers pour générer des planificateurs de stratégie. La panoplie d'outils proposée contient également des outils de simulation et d'analyse des planifications. Cet ensemble d'outils est utilisé pour determiner les stratégies permettant de résoudre certains problèmes générés par Isabelle/HOL.
Published: 2022

14. Activité pour apprendre la pensée computationnelle en mode branché et débranché

Author: Margarida ROMERO, Thierry Viéville, Marie Duflot-Kremer, Laboratoire d'Innovation et Numérique pour l'Education (LINE), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Université Côte d'Azur (UCA), Mnemonic Synergy (Mnemosyne), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut des Maladies Neurodégénératives [Bordeaux] (IMN), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), UCA - INSPE Académie de Nice, and MSc - SmartEdtech
Subjects: Unplugged activity, [SHS.EDU]Humanities and Social Sciences/Education, [INFO.INFO-GL]Computer Science [cs]/General Literature [cs.GL], Computational thinkink, Pedagogical robotics
Abstract: The introduction of computing into schools can drive the development of computational thinking along with associated problem-solving skills. In this context we look at the different types of activities used to learn computing, with the aim of establishing a protocol to compare plugged and unplugged activities at school, and more specifically to see how effectively unplugged activities can be used for skills transfer in order to learn computing.
Published: 2022

15. Automated Reasoning in the Class

Author: Drămnesc, Isabela, Ábrahám, Erika, Jebelean, Tudor, Kusper, Gábor, Stratulat, Sorin, West University of Timișoara [Roumanie] (WUT), Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), Johannes Kepler Universität Linz (JKU), Université Eszterházy Károly/Eszterházy Károly Egyetem [Eger, Hungary] (UEK/EKE), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), This work is co-funded by the Erasmus+ Programme of the European Union, project ARC: Automated Reasoning in the Class, 2019-1-RO01-KA203-063943., and Stratulat, Sorin
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [SHS.EDU]Humanities and Social Sciences/Education, [SHS.EDU] Humanities and Social Sciences/Education
Abstract: International audience
Published: 2022

16. Certified Derivation of Small-Step From Big-Step Skeletal Semantics

Author: Guillaume Ambal, Sergueï Lenglet, Alan Schmitt, Camille NoûS, Analyse sémantique et compilation pour la sécurité des environnements d'exécution (EPICURE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Laboratoire Cogitamus
Subjects: Big-Step, Small-Step, Operational Semantics, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Abstract: International audience; We present an automatic translation of a skeletal semantics written in big-step style into an equivalent structural operational semantics. This translation is implemented on top of the Necro tool, which lets us automatically generate an OCaml interpreter for the small step semantics and a Coq mechanization of both semantics. We prove the framework correct in two ways: we provide a paper proof of the core of the transformation, and we generate Coq certification scripts alongside the transformation. We illustrate the approach using a simple imperative language and show how it scales to larger languages.
Published: 2022

17. Experiments with Automated Reasoning in the Class

Author: Isabela Drămnesc, Erika Ábrahám, Tudor Jebelean, Gábor Kusper, Sorin Stratulat, West University of Timișoara [Roumanie] (WUT), Eszterházy Károly University, Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and This work is co-funded by the Erasmus+ Programme of the European Union, project ARC: Automated Reasoning in the Class, 2019-1-RO01-KA203-063943.
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computational Logic, Automated Reasoning, Computer Aided Teaching
Abstract: International audience; The European Erasmus+ project ARC-Automated Reasoning in the Class aims at improving the academic education in disciplines related to Computational Logic by using Automated Reasoning tools. We present the technical aspects of the tools as well as our education experiments, which took place mostly in virtual lectures due to the COVID pandemics. Our education goals are: to support the virtual interaction between teacher and students in the absence of the blackboard, to explain the basic Computational Logic algorithms, to study their implementation in certain programming environments, to reveal the main relationships between logic and programming, and to develop the proof skills of the students. For the introductory lectures we use some programs in C and in Mathematica in order to illustrate normal forms, resolution, and DPLL (Davis-Putnam-Logemann-Loveland) with its Chaff version, as well as an implementation of sequent calculus in the Theorema system. Furthermore we developed special tools for SAT (propositional satisfiability), some based on the original methods from the partners, including complex tools for SMT (Satisfiability Modulo Theories) that allow the illustration of various solving approaches. An SMT related approach is natural-style proving in Elementary Analysis, for which we developed and interesting set of practical heuristics. For more advanced lectures on rewrite systems we use the Coq programming and proving environment, in order on one hand to demonstrate programming in functional style and on the other hand to prove properties of programs. Other advanced approaches used in some lectures are the deduction based synthesis of algorithms and the techniques for program transformation.
Published: 2022

18. Foreword

Author: Matthew England, François Boulier, Timur Sadykov, Thomas Sturm, Coventry University, Université de Lille, Plekhanov Russian University of Economics [Moscow] (PRUE), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), and Max-Planck-Gesellschaft
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computational Mathematics, Computational Theory and Mathematics, Applied Mathematics
Abstract: International audience
Published: 2022

19. Non-Deterministic Abstract Machines

Author: Biernacka, Małgorzata, Biernacki, Dariusz, Lenglet, Serguei, Schmitt, Alan, Uniwersytet Wroclawski, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Inria, Lenglet, Sergueï, University of Wrocław [Poland] (UWr), Analyse sémantique et compilation pour la sécurité des environnements d'exécution (EPICURE), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)
Subjects: Theory of computation → Abstract machines, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, λ-calcul, process calculi, machines abstraites, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, calculs de processus, lambda-calculus, non-determinism, Abstract machines, [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]
Abstract: We present a generic design of abstract machines for nondeterministic programming languages, such as process calculi or concurrent lambda calculi, that provides a simple way to implement them. Such a machine traverses a term in the search for a redex, making non-deterministic choices when several paths are possible and backtracking when it reaches a dead end, i.e., an irreducible subterm. The search is guaranteed to terminate thanks to term annotations the machine introduces along the way. We show how to automatically derive a non-deterministic abstract machine from a zipper semantics-a form of structural operational semantics in which the decomposition process of a term into a context and a redex is made explicit. The derivation method ensures the soundness and completeness of the machines w.r.t. the zipper semantics., Nous proposons une présentation uniforme des machines abstraites pour les langages non déterministes, tels que les calculs de processus ou les lambda-calculs concurrents, qui permet de les implémenter facilement. Une telle machine traverse le terme à la recherche d’un redex, en faisant des choix arbitraires lorsque plusieurs chemins sont possibles, et en retournant en arrière lorsqu’elle atteint un cul-de-sac, c’est-à-dire un terme irreductible. Nous garantissons la terminaison de la recherche grâce aux annotations que la machine ajoute encours de route. Nous montrons comment dériver automatiquement une machine non déterministe depuis une sémantique zipper—une forme de sémantique opérationnelle structurelle dans laquelle la décomposition d’un terme en un contexte et un redex apparaît explicitement. La méthode dedérivation garantit la correction et la complétude de la machine par rapport à la sémantique zipper.
Published: 2022

20. Prophecy Made Simple

Author: Leslie Lamport, Stephan Merz, Microsoft Research (MSR), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: state machine, Program verification, Logic and verification, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], refinement, Formal specification, Software, auxiliary variable
Abstract: International audience; Prophecy variables were introduced in the article “The Existence of Refinement Mappings” by Abadi and Lamport. They were difficult to use in practice. We describe a new kind of prophecy variable that we find much easier to use. We also reformulate ideas from that article in a more mathematical way.
Published: 2022

21. ARC: An Educational Project on Automated Reasoning in the Class

Author: Drămnesc, Isabela, Jebelean, Tudor, Ábrahám, Erika, Kusper, Gábor, Stratulat, Sorin, West University of Timisoara, Computer Science Department, Johannes Kepler University Linz [Linz] (JKU), RTW Aachen, Eszterházy Károly University, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], education, [SHS.EDU]Humanities and Social Sciences/Education, computer science automated reasoning education problem based learning, computer science, problem based learning, automated reasoning
Abstract: International audience; The international Erasmus+ European Project: "ARC-Automated Reasoning in the Class", running from 2019 to 2022 is a partnership of universities from Austria, France, Germany, Hungary, and Romania, and has the purpose of developing advanced material for teaching subjects related to Computational Logic by using Automated Reasoning. The material includes a comprehensive textbook treating the necessary theoretical background (selected topics in Mathematical Logic), but mostly the practical methods from Automated Theorem Proving, as well as the description of the basic programming paradigms and the associated languages, in relation to their logical aspects. Furthermore, we address the most important applications, like program verification and testing, semantic representation of information, algorithm synthesis, etc. One of the main goals of the approach is to improve the logical background of the software professionals in order to motivate them to use formal methods for certification of complex systems and thus to avoid costly failures.
Published: 2022

22. Guaranteeing Timed Opacity using Parametric Timed Model Checking

Author: Étienne André, Dylan Marinho, Jun Sun, Didier Lime, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Laboratoire des Sciences du Numérique de Nantes (LS2N), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-École Centrale de Nantes (Nantes Univ - ECN), Nantes Université (Nantes Univ)-Nantes Université (Nantes Univ)-Nantes université - UFR des Sciences et des Techniques (Nantes univ - UFR ST), Nantes Université - pôle Sciences et technologie, Nantes Université (Nantes Univ)-Nantes Université (Nantes Univ)-Nantes Université - pôle Sciences et technologie, Nantes Université (Nantes Univ), School of Information Systems (Singapore Management University - SMU) (SIS - SMU), This work is partially supported by the ANR national research program PACS (ANR-14-CE28-0002), by the ANR-NRF research program ProMiS (ANR-19-CE25-0015), and by ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST., Agence Nationale de la Recherche (ANR), ANR-14-CE28-0002,PACS,Analyses paramétrées de systèmes concurrents(2014), and ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science - Cryptography and Security, parameter synthesis, Formal Languages and Automata Theory (cs.FL), opacity, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], parametric timed automata, Computer Science - Formal Languages and Automata Theory, Logic in Computer Science (cs.LO), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], timed automata, IMITATOR, Cryptography and Security (cs.CR), Software
Abstract: Information leakage can have dramatic consequences on systems security. Among harmful information leaks, the timing information leakage occurs whenever an attacker successfully deduces confidential internal information. In this work, we consider that the attacker has access (only) to the system execution time. We address the following timed opacity problem: given a timed system, a private location and a final location, synthesize the execution times from the initial location to the final location for which one cannot deduce whether the system went through the private location. We also consider the full timed opacity problem, asking whether the system is opaque for all execution times. We show that these problems are decidable for timed automata (TAs) but become undecidable when one adds parameters, yielding parametric timed automata (PTAs). We identify a subclass with some decidability results. We then devise an algorithm for synthesizing PTAs parameter valuations guaranteeing that the resulting TA is opaque. We finally show that our method can also apply to program analysis., This is the author version of the manuscript of the same name published in ACM Transactions on Software Engineering and Methodology (ToSEM). This work is partially supported by the ANR national research program PACS (ANR-14-CE28-0002), by the ANR-NRF research program ProMiS (ANR-19-CE25-0015), and by ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST. arXiv admin note: substantial text overlap with arXiv:1907.00537
Published: 2022

23. Timed automata as a formalism for expressing security: A survey on theory and practice

Author: Étienne André, Johan Arcile, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science - Cryptography and Security, General Computer Science, Formal Languages and Automata Theory (cs.FL), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Computer Science - Formal Languages and Automata Theory, Theoretical Computer Science, Logic in Computer Science (cs.LO), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], MESH: timed automata, MESH: cybersecurity, MESH: survey, MESH: attack trees, MESH: , opacity, Cryptography and Security (cs.CR)
Abstract: Timed automata are a common formalism for the verification of concurrent systems subject to timing constraints. They extend finite-state automata with clocks, that constrain the system behavior in locations, and to take transitions. While timed automata were originally designed for safety (in the wide sense of correctness w.r.t. a formal property), they were progressively used in a number of works to guarantee security properties. In this work, we review works studying security properties for timed automata in the last two decades. We notably review theoretical works, with a particular focus on opacity, as well as more practical works, with a particular focus on attack trees and their extensions. We derive main conclusions concerning open perspectives, as well as tool support., Comment: This is the author version of the manuscript of the same name published in ACM Computing Surveys
Published: 2022

24. Empowering the Event-B Method Using External Theories

Author: Yamine Aït-Ameur, Guillaume Dupont, Ismail Mendil, Dominique Méry, Marc Pantel, Peter Rivière, Neeraj K. Singh, Assistance à la Certification d’Applications DIstribuées et Embarquées (IRIT-ACADIE), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), TELECOM Nancy, Université de Lorraine (UL), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-CE25-0010,EBRP-EventB-Rodin-Plus,Enrichissement de EventB et de RODIN : EventB-Rodin-Plus(2019)
Subjects: [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Event-B, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], Safety, State-based methods, Partial definitions and well-definedness, Invariants preservation
Abstract: International audience; Event-B offers a rigorous state-based framework for designing critical systems. Models describe state changes (transitions), and invariant preservation is ensured by inductive proofs over execution traces. In a correct model, such changes transform safe states into safe states, effectively defining a partial function, whose domain prevents ill-defined state changes. Moreover, a state can be formalised as a complex data type, and as such it is accompanied by operators whose correct use is ensured by well-definedness (WD) conditions (partial functions).This paper proposes to define transitions explicitly as partial functions in an Event-B theory. WD conditions associated to these functions prevent ill-defined transitions in a more effective way than usual Event-B events. We advocate that these WD conditions are sufficient to define transitions that preserve (inductive) invariants and safety properties, thus providing easier and reusable proof methods for model invariant preservation. We rely on the finite automata example to illustrate our approach.
Published: 2022

25. Selected papers from The 13th International Symposium on Theoretical Aspects of Software Engineering 29 July – 1 August 2019, Guilin, China

Author: Dominique Méry, Shengchao Qin, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), TELECOM Nancy, Université de Lorraine (UL), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Teeside University., and University Teeside
Subjects: [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], Software
Abstract: International audience
Published: 2022

26. The central role of data repositories and data models in Data Science and Advanced Analytics

Author: Dominique Méry, El Hassan Abdelwahed, Matteo Golfarelli, Ladjel Bellatreche, Carlos Ordonez, Laboratoire d'Informatique et d'Automatique pour les Systèmes (LIAS), Université de Poitiers-Ecole Nationale Supérieure de Mécanique et d'Aérotechnique [Poitiers] (ISAE-ENSMA), University of Houston, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), TELECOM Nancy, Université de Lorraine (UL), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), University of Bologna/Università di Bologna, and Université Cadi Ayyad [Marrakech] (UCA)
Subjects: Value (ethics), Computer Networks and Communications, Computer science, media_common.quotation_subject, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], Advanced Analytics, Data modeling, Distributed data storage, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Added value, Quality (business), Knowledge Graphs, media_common, Smart system, Model engineering, business.industry, Formal methods, Data Science, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Data science workflow, Data science, Model driven engineering, Workflow, Hardware and Architecture, Analytics, Accountability, Distributed algorithms, business, Software, Value
Abstract: International audience; In the age of “Data Science and Advanced Analytics”, we are witnessing a race for developing data-driven smart systems in various domains such as business, finance, healthcare, environment, cybersecurity, etc. due the explosion of the data issued by various providers. This development contributes in getting added value for companies and citizens. Two complementary ingredients are required for ensuring valuable systems: data and models. The data dimension is mainly related to Data Science that unifies machine learning, statistics, data mining, databases, and distributed systems. The achievement of this value may pass through the augmentation of input data by resources such as Knowledge Graphs. The success of the above techniques strongly depends on the quality of the input data and the consideration of other non-functional properties related to legal, ethical, and economical aspects. On the other hand, modeling plays a crucial role in Data Science since it covers all steps of Data Science workflow. Regarding data provenance and its quality, models contribute to providing vendor-independent solutions. At the algorithmic level, models help in explaining the inner working of the used methods/algorithms to system designers, users, regulators, and citizens to achieve trust and accountability. Therefore, the success of Data Science depends on our skill to use it a smart way and simultaneously exploiting data and modeling capabilities.
Published: 2022

27. On the Benefits of Using MVC Pattern for Structuring Event-B Models of WIMP Interactive Applications

Author: Neeraj Kumar Singh, Yamine Aït-Ameur, Philippe Palanque, Romain Geniet, Dominique Méry, Assistance à la Certification d’Applications DIstribuées et Embarquées (IRIT-ACADIE), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Rennes (UR), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), TELECOM Nancy, Université de Lorraine (UL), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse III - Paul Sabatier (UT3), Interactive Critical Systems (IRIT-ICS), ANR-16-CE25-0007,FORMEDICIS,Méthodes formelles pour le développement et l'ingénierie de systèmes interactifs critiques(2016), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Source code, Correctness, Computer science, media_common.quotation_subject, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Automotive industry, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], 02 engineering and technology, Structuring, Domain (software engineering), [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Control theory, 0202 electrical engineering, electronic engineering, information engineering, 0501 psychology and cognitive sciences, MESH: formal method, 050107 human factors, media_common, MESH: MVC, Event (computing), business.industry, 05 social sciences, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, Human-Computer Interaction, MESH: HMI, Scalability, MESH: Event-B, MESH: WIMP, Software engineering, business, Software
Abstract: This paper presents a formal development approach for designing interactive applications using a correct-by-construction approach. In this work, we propose a refinement strategy using model-view-controller (MVC) to structure and design Event-B formal models of the interactive application. The proposed MVC-based refinement strategy facilitates the development of an abstract model and a series of refined models by introducing the possible modes, controller’s behaviour and visual components of the interactive application while preserving the required interaction-related safety properties. To demonstrate the effectiveness, scalability, reliability and feasibility of our approach, we use a small example (from automotive domain) and real-life industrial case studies (from aviation). The entire development is realized in Event-B and the associated Rodin tool is used to analyse and verify the correctness of the formalized model. Finally, the developed Event-B models are used to generate source code using EB2ALL tool for going from the specification to the implementation of the interactive application.
Published: 2021

28. An Approximation of Minimax Control using Random Sampling and Symbolic Computation

Author: Étienne André, Laurent Fribourg, Jawher Jerray, Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), and Max-Planck-Gesellschaft-Max-Planck-Gesellschaft
Subjects: 0209 industrial biotechnology, 021103 operations research, bounded uncertainty, random sampling, 0211 other engineering and technologies, Euler's method, Perturbation (astronomy), Value (computer science), 02 engineering and technology, State (functional analysis), Symbolic computation, Minimax, Domain (mathematical analysis), optimal control, 020901 industrial engineering & automation, Control and Systems Engineering, Bounded function, [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], Applied mathematics, Switched systems, SIMPLE algorithm, Mathematics
Abstract: This manuscript is published in the proceedings of the 7th IFAC Conference on Analysis and Design of Hybrid Systems (ADHS 2021).; International audience; We aim at the synthesis of an approximate minimax control for a system dynamic given in the form x.(t) = f(x(t),u(t),d(t)) where x represents the state, u the control (or input) and d a disturbance (or perturbation).The disturbance d(t) is prescribed to a compact domain D on which it can take any value (bounded uncertainty).Our method makes use of symbolic computation to enclose the solutions corresponding to all possible disturbance d. in D, together with a simple algorithm of random sampling to select the minimum control u*.We illustrate the interest of this approximate minimax control on an example of a biochemical reactor.
Published: 2021

29. Exemplifying parametric timed specifications over signals with bounded behavior

Author: Étienne André, Masaki Waga, Natuski Urabe, Ichiro Hasuo, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Kyoto University, National Institute of Informatics (NII), Graduate University for Advanced Studies [Hayama] (SOKENDAI), This work is partially supported by ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST and by the ANR-NRF French-Singaporean research program ProMiS (ANR-19-CE25-0015)., Klaus Havelund, Jyo Deshmukh, Ivan Perez, ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST, and ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, specification, Formal Languages and Automata Theory (cs.FL), timed automata, hybrid automata, signals, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Computer Science - Formal Languages and Automata Theory, Computer Science::Formal Languages and Automata Theory, Logic in Computer Science (cs.LO)
Abstract: Specifying properties can be challenging work. In this paper, we propose an automated approach to exemplify properties given in the form of automata extended with timing constraints and timing parameters, and that can also encode constraints over real-valued signals. That is, given such a specification and given an admissible automaton for each signal, we output concrete runs exemplifying real (or impossible) runs for this specification. Specifically, our method takes as input a specification, and a set of admissible behaviors, all given as a subclass of rectangular hybrid automata, namely timed automata extended with arbitrary clock rates, signal constraints, and timing parameters. Our method then generates concrete runs exemplifying the specification., This is the author (and extended) version of the manuscript of the same name published in the proceedings of the 14th NASA Formal Methods Symposium (NFM 2022). This work is partially supported by ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST and by the ANR-NRF French-Singaporean research program ProMiS (ANR-19-CE25-0015)
Published: 2022

30. A tier-based typed programming language characterizing Feasible Functionals

Author: Bruce M. Kapron, Romain Péchoux, Jean-Yves Marion, Emmanuel Hainry, Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), University of Victoria [Canada] (UVIC), Carbone (CARBONE), Department of Formal Methods (LORIA - FM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], tiering, Computer Science - Logic in Computer Science, General Computer Science, Computer science, Inference, implicit computational complexity, 0102 computer and information sciences, 02 engineering and technology, Type (model theory), computer.software_genre, 01 natural sciences, type-2, Oracle, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Theoretical Computer Science, type system, 0202 electrical engineering, electronic engineering, information engineering, Time complexity, Class (computer programming), Computer Science - Programming Languages, Programming language, Type inference, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Logic in Computer Science (cs.LO), Decidability, Imperative programming, Feasible functionals, 010201 computation theory & mathematics, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, BFF, computer, Programming Languages (cs.PL)
Abstract: International audience; The class of Basic Feasible Functionals BFF$_2$ is the type-2 counterpart of the class FP of type-1 functions computable in polynomial time. Several characterizations have been suggested in the literature, but none of these present a programming language with a type system guaranteeing this complexity bound. We give a characterization of BFF$_2$ based on an imperative language with oracle calls using a tier-based type system whose inference is decidable. Such a characterization should make it possible to link higher-order complexity with programming theory. The low complexity (cubic in the size of the program) of the type inference algorithm contrasts with the intractability of the aforementioned methods and does not overly constrain the expressive power of the language.
Published: 2022

31. ODEbase: A Repository of ODE Systems for Systems Biology

Author: Christoph Lüders, Thomas Sturm, Ovidiu Radulescu, University of Kassel, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Max-Planck-Gesellschaft, Centre National de la Recherche Scientifique (CNRS), Université de Montpellier (UM), and ANR-17-CE40-0036,SYMBIONT,Méthodes symboliques pour les réseaux biologiques(2017)
Subjects: FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, Molecular Networks (q-bio.MN), FOS: Biological sciences, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [SDV.BBM.MN]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], Quantitative Biology - Molecular Networks, General Medicine, Symbolic Computation (cs.SC)
Abstract: Summary Recently, symbolic computation and computer algebra systems have been successfully applied in systems biology, especially in chemical reaction network theory. One advantage of symbolic computation is its potential for qualitative answers to biological questions. Qualitative methods analyze dynamical input systems as formal objects, in contrast to investigating only part of the state space, as is the case with numerical simulation. However, corresponding tools and libraries have a different set of requirements for their input data than their numerical counterparts. A common format used in mathematical modeling of biological processes is Systems Biology Markup Language (SBML). We illustrate that the use of SBML data in symbolic computation requires significant pre-processing, incorporating external biological and mathematical expertise. ODEbase provides suitable input data derived from established existing biomodels, covering in particular the BioModels database. Availability and implementation ODEbase is available free of charge at https://odebase.org.
Published: 2022

32. Certified Abstract Machines for Skeletal Semantics

Author: Ambal, Guillaume, Lenglet, Sergueï, Schmitt, Alan, Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Analyse sémantique et compilation pour la sécurité des environnements d'exécution (EPICURE), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)
Subjects: [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Operational Semantics, 0202 electrical engineering, electronic engineering, information engineering, 020207 software engineering, Abstract Machines, 0102 computer and information sciences, 02 engineering and technology, Skeletal Semantics, 01 natural sciences, Certified Interpretation
Abstract: International audience; Skeletal semantics is a framework to describe semantics of programming languages. We propose an automatic generation of a certified OCaml interpreter for any language written in skeletal semantics. To this end, we introduce two new interpretations, i.e., formal meanings, of skeletal semantics, in the form of non-deterministic and deterministic abstract machines. These machines are derived from the usual bigstep interpretation of skeletal semantics using functional correspondence, a standard transformation from big-step evaluators to abstract machines. All these interpretations are formalized in the Coq proof assistant and we certify their soundness. We finally use the extraction from Coq to OCaml to obtain the certified interpreter.
Published: 2022

33. F5: A REDUCE Package for Signature-based Gröbner Basis Computation

Author: Demin, Alexander, Rahkooy, Hamid, Sturm, Thomas, Sturm, Thomas, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Saarland University [Saarbrücken]
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [MATH.MATH-AG] Mathematics [math]/Algebraic Geometry [math.AG], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG]
Abstract: International audience
Published: 2022

34. Analyse statique de transformations pour l'élimination de motifs

Author: Lermusiaux, Pierre, LERMUSIAUX, Pierre, Université de Lorraine (UL), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Pierre-Etienne Moreau, and Horatiu Cirstea
Subjects: analyse statique, sémantique de motif, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], pattern semantics, program transforma-tion, rewriting, [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL], filtrage par motif, pattern matching, static analysis, spécification algébrique, transformation de programmes, algebraic specifications, réécriture
Abstract: Program transformation is an extremely common practice in computer science. From compilation to tests generation, through many approaches of code analysis and formal verification of programs, it is a process that is both ubiquitous and critical to properly functioning programs and information systems. This thesis proposes to study the program transformations mechanisms in order to express and verify syntactical guarantees on the behaviour of these transformations and on their results.Giving a characterisation of the shape of terms returned by such a transformation is, indeed, a common approach to the formal verification of programs. In order to express some properties often used by this type of approaches, we propose in this thesis a formalism inspired by themodel of compilation passes, which are used to describe the general compilation of a program as a sequence of minimal transformations, and based on the notions of pattern matching and term rewriting.This formalism relies on an annotation mechanism of function symbols in order to express a set of specifications describing the behaviours of the associated functions. We then propose a static analysis method in order to check that a transformation, expressed as a term rewritesystem, actually verifies its specifications., La transformation de programmes est une pratique très courante dans le domaine des sciences informatiques. De la compilation à la génération de test en passant par de nombreuses approches d’analyse de codes et de vérification formelle des programmes, c’est un procédé qui est à la fois omniprésent et crucial au bon fonctionnement des programmes et systèmes informatiques. Cette thèse propose une étude formelle des procédures de transformation de programmes dans le but d’exprimer et de garantir des propriétés syntaxiques sur le comportement et les résultats d’unetelle transformation.Dans le contexte de la vérification formelle des programmes, il est en effet souvent nécessaire de pouvoir caractériser la forme des termes obtenus par réduction suivant une telle transformation. En s’inspirant du modèle de passes de compilation, qui décrivent un séquençage de la compilation d’un programme en étapes de transformation minimales n’affectant qu’un petit nombre des constructions du langage, on introduit, dans cette thèse, un formalisme basé sur les notions de filtrage par motif et de réécriture permettant de décrire certaines propriétés couramment induites par ce type de transformations.Le formalisme proposé se repose sur un système d’annotations des symboles de fonction décrivant une spécification du comportement attendu des fonctions associées. On présente alors une méthode d’analyse statique permettant de vérifier que les transformations étudiées, exprimées par un système de réécriture, satisfont en effet ces spécifications.
Published: 2022

35. Efficient Convex Zone Merging in Parametric Timed Automata

Author: J.C. Van de Pol, Étienne André, Dylan Marinho, Laure Petrucci, Bogomolov, Sergiy, Parker, David, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Department of Computer Science [Aarhus], This work is partially supported by the ANR-NRF French-Singaporean research program ANR-19-CE25-0015 and CNRS-INS2I project TrAVAIL., Sergiy Bogomolov, David Parker, CNRS-INS2I project TrAVAIL, and ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, parameter synthesis, parametric timed model checking, convex merging, Formal Languages and Automata Theory (cs.FL), [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], parametric timed automata, IMITATOR, Computer Science - Formal Languages and Automata Theory, model checking, Logic in Computer Science (cs.LO)
Abstract: Parametric timed automata are a powerful formalism for reasoning on concurrent real-time systems with unknown or uncertain timing constants. Reducing their state space is a significant way to reduce the inherently large analysis times. We present here different merging reduction techniques based on convex union of constraints (parametric zones), allowing to decrease the number of states while preserving the correctness of verification and synthesis results. We perform extensive experiments, and identify the best heuristics in practice, bringing a significant decrease in the computation time on a benchmarks library., Comment: This is the author version of the manuscript of the same name published in the proceedings of the 20th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2022)
Published: 2022
Full Text: View/download PDF

36. Complete and tractable machine-independent characterizations of second-order polytime

Author: Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion, Romain Péchoux, Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), University of Victoria [Canada] (UVIC), Carbone (CARBONE), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and NSERC RGPIN-2021-02481
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], FOS: Computer and information sciences, Computer Science - Logic in Computer Science, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Computer Science - Programming Languages, MathematicsofComputing_GENERAL, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Basic feasible functionals, Computational Complexity (cs.CC), Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Safe recursion, Polynomial time, Tiering, Second-order, Type 2, Programming Languages (cs.PL)
Abstract: The class of Basic Feasible Functionals $$\mathtt{BFF}$$ BFF is the second-order counterpart of the class of first-order functions computable in polynomial time. We present several implicit characterizations of $$\mathtt{BFF}$$ BFF based on a typed programming language of terms. These terms may perform calls to imperative procedures, which are not recursive. The type discipline has two layers: the terms follow a standard simply-typed discipline and the procedures follow a standard tier-based type discipline. $$\mathtt{BFF}$$ BFF consists exactly of the second-order functionals that are computed by typable and terminating programs. The completeness of this characterization surprisingly still holds in the absence of lambda-abstraction. Moreover, the termination requirement can be specified as a completeness-preserving instance, which can be decided in time quadratic in the size of the program. As typing is decidable in polynomial time, we obtain the first tractable (i.e., decidable in polynomial time), sound, complete, and implicit characterization of $$\mathtt{BFF}$$ BFF , thus solving a problem opened for more than 20 years.
Published: 2022
Full Text: View/download PDF

37. Reduction of Chemical Reaction Networks with Approximate Conservation Laws

Author: Desoeuvres, Aurélien, Iosif, Alexandru, Lüders, Christoph, Radulescu, Ovidiu, Rahkooy, Hamid, Seiß, Matthias, Sturm, Thomas, Sturm, Thomas, Laboratory of Pathogen Host Interactions [Montpellier] (LPHI), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), IE University [Campus Madrid], Universität Bonn = University of Bonn, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, University of Kassel, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)
Subjects: [SDV] Life Sciences [q-bio], 34E13, 37D10, 37N25, 14-04, 92C45, 34C14, [SDV]Life Sciences [q-bio], Molecular Networks (q-bio.MN), FOS: Biological sciences, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], FOS: Mathematics, [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], Quantitative Biology - Molecular Networks, Dynamical Systems (math.DS), Mathematics - Dynamical Systems
Abstract: Model reduction of fast-slow chemical reaction networks based on the quasi-steady state approximation fails when the fast subsystem has first integrals. We call these first integrals approximate conservation laws. In order to define fast subsystems and identify approximate conservation laws, we use ideas from tropical geometry. We prove that any approximate conservation law evolves slower than all the species involved in it and therefore represents a supplementary slow variable in an extended system. By elimination of some variables of the extended system, we obtain networks without approximate conservation laws, which can be reduced by standard singular perturbation methods. The field of applications of approximate conservation laws covers the quasi-equilibrium approximation, well known in biochemistry. We discuss both two timescale reductions of fast-slow systems and multiple timescale reductions of multiscale networks. Networks with multiple timescales have hierarchical relaxation. At a given timescale, our multiple timescale reduction method defines three subsystems composed of (i) slaved fast variables satisfying algebraic equations, (ii) slow driving variables satisfying reduced ordinary differential equations, and (iii) quenched much slower variables that are constant. The algebraic equations satisfied by fast variables define chains of nested normally hyberbolic invariant manifolds. In such chains, faster manifolds are of higher dimension and contain the slower manifolds. Our reduction methods are introduced algorithmically for networks with linear, monomial or polynomial approximate conservation laws. Keywords: Model order reduction, chemical reaction networks, singular perturbations, multiple timescales, tropical geometry.
Published: 2022

38. Offline and Online Monitoring of Scattered Uncertain Logs Using Uncertain Linear Dynamical Systems

Author: Étienne André, Bineet Ghosh, University of North Carolina [Chapel Hill] (UNC), University of North Carolina System (UNC), Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), This work is partially supported by the ANR-NRF French-Singaporean research program ProMiS (ANR-19-CE25-0015), and the National Science Foundation (NSF) of the United States of America under grant number 2038960, Mohammad Mousavi and Anna Philippou, and ANR-19-CE25-0015,ProMiS,Mitigation formelle d'attaques via canaux auxiliaires par vérification paramétrée(2019)
Subjects: offline monitoring, monitoring, formal methods, [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], cyber-physical systems, energy-aware monitoring
Abstract: This is the author version of the manuscript of the same name published in the proceedings of FORTE 2022.; International audience; Monitoring the correctness of distributed cyber-physical systems is essential. We address the analysis of the log of a black-box cyber-physical system. Detecting possible safety violations can be hard when some samples are uncertain or missing. In this work, the log is made of values known with some uncertainty; in addition, we make use of an over-approximated yet expressive model, given by a non-linear extension of dynamical systems. Given an offline log, our approach is able to monitor the log against safety specifications with a limited number of false alarms. As a second contribution, we show that our approach can be used online to minimize the number of sample triggers, with the aim at energetic efficiency. We apply our approach to two benchmarks, an anesthesia model and an adaptive cruise controller.
Published: 2022

39. Foreword, with a Dedication to Vladimir Gerdt

Author: Matthew England, François Boulier, Timur Sadykov, Thomas Sturm, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, ANR-17-CE40-0036,SYMBIONT,Méthodes symboliques pour les réseaux biologiques(2017), Coventry University, Université de Lille, Plekhanov Russian University of Economics [Moscow] (PRUE), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Applied Mathematics, media_common.quotation_subject, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [SDV.BBM.MN]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], Art, Article, Computational Mathematics, Computational Theory and Mathematics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], ComputingMilieux_MISCELLANEOUS, Classics, media_common
Abstract: International audience
Published: 2021

40. A complete and terminating approach to linear integer solving

Author: Thomas Sturm, Martin Bromberger, Christoph Weidenbach, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Saarland University [Saarbrücken], Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft, and Universität des Saarlandes [Saarbrücken]
Subjects: Normalization property, CDCL, Algebra and Number Theory, 010102 general mathematics, Linear arithmetic, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Context (language use), 010103 numerical & computational mathematics, Integer arithmetic, Space (mathematics), 01 natural sciences, Satisfiability, Decidability, Algebra, Computational Mathematics, SMT, Linear programming, Quantifier elimination, Order (group theory), SAT, [INFO]Computer Science [cs], 0101 mathematics, Integer (computer science), Mathematics
Abstract: International audience; We consider feasibility of linear integer problems in the context of verification systems such as SMT solvers or theorem provers. Although satisfiability of linear integer problems is decidable, many state-of-the-art implementations neglect termination in favor of efficiency. We present thecalculus CutSat++ that is sound, terminating, complete, and leaves enough space for model assumptions and simplification rules in order to be efficient in practice. CutSat++ combines model-driven reasoning and quantifier elimination to the feasibility of linear integer problems.
Published: 2020

41. Identifying the parametric occurrence of multiple steady states for some biological networks

Author: Marek Košta, Matthew England, Dima Grigoriev, Ovidiu Radulescu, Hassan Errami, Russell Bradford, Vladimir P. Gerdt, Thomas Sturm, James H. Davenport, Andreas Weber, Charles Tapley Hoyt, Department of Computer Science [Bath], University of Bath [Bath], Coventry University (UK), Coventry University, Institut für Informatik II [Bonn], Rheinische Friedrich-Wilhelms-Universität Bonn, Joint Institute for Nuclear Research (JINR), Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Bonn-Aachen International Center for Information Technology (B-IT), Rheinisch-Westfälische Technische Hochschule Aachen (RWTH)-University of Applied Sciences Bonn-Rhein-Sieg-Fraunhofer (Fraunhofer-Gesellschaft)-University of Bonn, Slovak Academy of Sciences (SAS), Université de Montpellier (UM), Universität des Saarlandes [Saarbrücken], Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), ANR-17-CE40-0036,SYMBIONT,Méthodes symboliques pour les réseaux biologiques(2017), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS), Universität Bonn = University of Bonn-Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH)-Fraunhofer (Fraunhofer-Gesellschaft)-University of Applied Sciences Bonn-Rhein-Sieg, Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Saarland University [Saarbrücken]
Subjects: Computer Science - Symbolic Computation, FOS: Computer and information sciences, [SDV]Life Sciences [q-bio], Structure (category theory), Mixed equation/inequality solving, 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), Parameter space, Signaling Pathways, 01 natural sciences, Signalling pathways, symbols.namesake, Gaussian elimination, Real quantifier elimination, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [INFO]Computer Science [cs], [MATH]Mathematics [math], 0101 mathematics, Parametric statistics, Mathematics, I.1.4, Biological Networks, Algebra and Number Theory, Biological networks, 010102 general mathematics, Graph theory, Symbolic computation, MAPK, Cylindrical algebraic decomposition, Computational Mathematics, symbols, Algorithm, Mixed Equation / Inequality Solving, Biological network
Abstract: We consider a problem from biological network analysis of determining regions in a parameter space over which there are multiple steady states for positive real values of variables and parameters. We describe multiple approaches to address the problem using tools from Symbolic Computation. We describe how progress was made to achieve semi-algebraic descriptions of the multistationarity regions of parameter space, and compare symbolic results to numerical methods. The biological networks studied are models of the mitogen-activated protein kinases (MAPK) network which has already consumed considerable effort using special insights into its structure of corresponding models. Our main example is a model with 11 equations in 11 variables and 19 parameters, 3 of which are of interest for symbolic treatment. The model also imposes positivity conditions on all variables and parameters. We apply combinations of symbolic computation methods designed for mixed equality/inequality systems, specifically virtual substitution, lazy real triangularization and cylindrical algebraic decomposition, as well as a simplification technique adapted from Gaussian elimination and graph theory. We are able to determine multistationarity of our main example over a 2-dimensional parameter space. We also study a second MAPK model and a symbolic grid sampling technique which can locate such regions in 3-dimensional parameter space., Comment: 60 pages - author preprint. Accepted in the Journal of Symbolic Computation
Published: 2020

42. TLA+ model checking made symbolic

Author: Igor Konnov, Thanh-Hai Tran, Jure Kukovec, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Vienna University of Technology (TU Wien), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), and Max-Planck-Gesellschaft-Max-Planck-Gesellschaft
Subjects: Model checking, Exploit, Relation (database), Computer science, Programming language, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], 02 engineering and technology, computer.software_genre, Language primitive, TLA+, SMT, 020204 information systems, Formal specification, 0202 electrical engineering, electronic engineering, information engineering, State (computer science), Tuple, Safety, Risk, Reliability and Quality, Boolean data type, computer, Software
Abstract: TLA+ is a language for formal specification of all kinds of computer systems. System designers use this language to specify concurrent, distributed, and fault-tolerant protocols, which are traditionally presented in pseudo-code. TLA+ is extremely concise yet expressive: The language primitives include Booleans, integers, functions, tuples, records, sequences, and sets thereof, which can be also nested. This is probably why the only model checker for TLA+ (called TLC) relies on explicit enumeration of values and states. In this paper, we present APALACHE -- a first symbolic model checker for TLA+. Like TLC, it assumes that all specification parameters are fixed and all states are finite structures. Unlike TLC, APALACHE translates the underlying transition relation into quantifier-free SMT constraints, which allows us to exploit the power of SMT solvers. Designing this translation is the central challenge that we address in this paper. Our experiments show that APALACHE outperforms TLC on examples with large state spaces.
Published: 2019

43. MEMOCODE '21: Proceedings of the 19th ACM-IEEE International Conference on Formal Methods and Models for System Design

Author: S, Arunkumar, Méry, Dominique, Saha, Indranil, Zhang, Lijun, Indian Institute of Technology Delhi (IIT Delhi), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), TELECOM Nancy, Université de Lorraine (UL), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), University of California (UC), and Institute of Software Chinese Academy of Sciences [Beijing]
Subjects: [INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR], [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE]
Abstract: International audience; MEMOCODE brings together researchers and practitioners interested in formal methods for system design and development to exchange research results and lessons learned. The conference focuses on the foundations and applications of formal methods in the development of hardware, firmware, middleware, and application software for systems ranging from single embedded devices to highly networked cyber-physical systems and the Internet of Things.
Published: 2021

44. Synchronization Modulo k in Dynamic Networks

Author: Louis Penet de Monterno, Bernadette Charron-Bost, Stephan Merz, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Colette Johnen and Elad Michael Schiller and Stefan Schmid, Département d'informatique - ENS Paris (DI-ENS), Department of Formal Methods (LORIA - FM), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft, École normale supérieure - Paris (ENS-PSL), Analyse Statique par Interprétation Abstraite (ANTIQUE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Proof-oriented development of computer-based systems (MOSEL), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Colette Johnen, Elad Michael Schiller, and Stefan Schmid
Subjects: 03 medical and health sciences, 0302 clinical medicine, 010201 computation theory & mathematics, 030220 oncology & carcinogenesis, [INFO]Computer Science [cs], 0102 computer and information sciences, 01 natural sciences
Abstract: International audience; We define the mod k-synchronization problem as a weakening of the Firing Squad problem, where all nodes fire not at the same round, but at rounds that are all equal modulo k. We propose an algorithm that achieves mod k-synchronization in any dynamic network where there exist – possibly several – fixed spanning stars within each period of Delta consecutive rounds. In other words, we require that there always exists a temporal path of length at most Delta between some fixed node gamma and every other node. As opposed to the perfect synchronization achieved in the Firing Squad problem, mod k-synchronization thus does not require any strong connectivity property in the network. In our algorithm, all the nodes "know'' Delta, but they ignore what nodes are the centers of the spanning stars. We also prove that if the bound Delta for guaranteeing fixed spanning stars exists but is unknown to the agents, then mod k-synchronization is impossible.All nodes in our algorithm fire in less that 6kn + 4k rounds after all nodes become active, but unfortunately use unbounded counters. We then propose a refinement of this algorithm so that it becomes finite state while maintaining the same time complexity. The correctness of our first algorithm has been formally established in the proof assistant Isabelle.
Published: 2021

45. Alethe: Towards a Generic SMT Proof Format (extended abstract)

Author: Pascal Fontaine, Hans-Jörg Schurr, Haniel Barbosa, Mathias Fleury, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft, Proof-oriented development of computer-based systems (MOSEL), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Johannes Kepler University Linz [Linz] (JKU), Universidade Federal de Minas Gerais [Belo Horizonte] (UFMG), Université de Liège, European Project: 713999,H2020,Matryoshka(2017), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Johannes Kepler Universität Linz - Johannes Kepler University Linz [Autriche] (JKU)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, I.2.3, Computer science, Programming language, Multiple applications, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, 02 engineering and technology, Mathematical proof, computer.software_genre, Logic in Computer Science (cs.LO), 03 medical and health sciences, 0302 clinical medicine, 030220 oncology & carcinogenesis, Satisfiability modulo theories, 0202 electrical engineering, electronic engineering, information engineering, computer
Abstract: The first iteration of the proof format used by the SMT solver veriT was presented ten years ago at the first PxTP workshop. Since then the format has matured. veriT proofs are used within multiple applications, and other solvers generate proofs in the same format. We would now like to gather feedback from the community to guide future developments. Towards this, we review the history of the format, present our pragmatic approach to develop the format, and also discuss problems that might arise when other solvers use the format., In Proceedings PxTP 2021, arXiv:2107.01544
Published: 2021

46. E-Cyclist: Implementation of an Efficient Validation of FOL ID Cyclic Induction Reasoning (Tool Description)

Author: Stratulat, Sorin, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), and Max-Planck-Gesellschaft-Max-Planck-Gesellschaft
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS
Abstract: International audience; Checking the soundness of cyclic induction reasoning for first-order logic with inductive definitions (FOLID) is decidable but the standard checking method is based on an exponential complement operation for Büchi automata. Recently, we introduced a polynomial checking method whose most expensive steps recall the comparisons done with multiset path orderings. We describe the implementation of our method in the Cyclist prover. Referred to as E-Cyclist, it successfully checked all the proofs included in the original distribution of Cyclist. Heuristics have been devised to automatically define, from the analysis of the proof derivations, the trace-based ordering measures that guarantee the soundness property.
Published: 2021

47. Static analysis of pattern-free properties

Author: Pierre-Etienne Moreau, Pierre Lermusiaux, Horatiu Cirstea, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and ANR-16-CE25-0007,FORMEDICIS,Méthodes formelles pour le développement et l'ingénierie de systèmes interactifs critiques(2016)
Subjects: Pattern-matching, Rewriting, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Formalism (philosophy), Semantics (computer science), Computer science, Programming language, 020207 software engineering, Context (language use), 0102 computer and information sciences, 02 engineering and technology, Term (logic), Static analysis, computer.software_genre, 01 natural sciences, Pattern semantics, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 0202 electrical engineering, electronic engineering, information engineering, Pattern matching, computer, Formal verification
Abstract: International audience; Rewriting is a widely established formalism with major applications in computer science. It is indeed a staple of many formal verification applications as it is especially well suited to describe program semantics and transformations. In particular, constructor based term rewriting systems are generally used to illustrate the behaviour of functional programs.In the context of formal verification, it is often necessary to characterize the shape of the reducts of such rewrite systems and, in a typed context, the underlying type system provides syntactic guarantees on the form of these terms by exhibiting, among others, the constructor symbols that they can contain. On the other hand, when performing (program) transformations we often want to eliminate some symbols and, more generally, to ensure that some patterns are absent from the result of the transformation.We propose in this paper an approach to statically verify the absence of specified patterns from the reachable terms of constructor based term rewriting systems. The proposed approach consists in annotating the function symbols with a set of profiles outlining pre- and post-conditions that must be verified by the rewrite relation, and using a rewrite based method to statically verify that the rewrite system is indeed consistent with the respective annotations.
Published: 2021

48. Algorithmic Reduction of Biological Networks with Multiple Time Scales

Author: Ovidiu Radulescu, Sebastian Walcher, Christoph Lüders, Thomas Sturm, Niclas Kruff, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, ANR-17-CE40-0036,SYMBIONT,Méthodes symboliques pour les réseaux biologiques(2017), Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), Rheinische Friedrich-Wilhelms-Universität Bonn, Dynamique des interactions membranaires normales et pathologiques (DIMNP), Université Montpellier 1 (UM1)-Université Montpellier 2 - Sciences et Techniques (UM2)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université de Montpellier (UM), Centre National de la Recherche Scientifique (CNRS), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Saarland University [Saarbrücken], Sturm, Thomas, Méthodes symboliques pour les réseaux biologiques - - SYMBIONT2017 - ANR-17-CE40-0036 - AAPG2017 - VALID, RWTH Aachen University, University of Bonn, LPHI - Laboratory of Pathogen Host Interactions (LPHI), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft, This work has been supported by the interdisciplinary bilateral project ANR-17-CE40-0036/DFG391322026 SYMBIONT., Universität Bonn = University of Bonn, and Laboratory of Pathogen Host Interactions [Montpellier] (LPHI)
Subjects: FOS: Computer and information sciences, Computer Science - Symbolic Computation, 37D10, Computer Science - Logic in Computer Science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Computer science, Molecular Networks (q-bio.MN), Dynamical Systems (math.DS), 92C45, 01 natural sciences, Real algebraic computation, Secondary 14P10, Symbolic computation, Satisfiability modulo theories, Logic computation, Quantitative Biology - Molecular Networks, Invariant (mathematics), Mathematics - Dynamical Systems, Singular perturbation, Invariant set, Multiple time scales, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Sequence, Polynomial differential equations, Applied Mathematics, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], BioModels Database, [MATH.MATH-AG] Mathematics [math]/Algebraic Geometry [math.AG], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [SDV.BBM.MN]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], Computational Mathematics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Dimension reduction, Tropical geometry Mathematics Subject Classification Primary 68W30, Chemical reaction network, Dynamical systems theory, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], 0102 computer and information sciences, Symbolic Computation (cs.SC), FOS: Mathematics, 0101 mathematics, 010102 general mathematics, 68W30 (Primary), 14P10, 34E15, 37D10, 92C45 (Secondary), 34E15, Compartmental model, Logic in Computer Science (cs.LO), Algebra, [SDV.BBM.MN] Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], FOS: Biological sciences, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], ddc:004, Biological network
Abstract: Mathematics in computer science 15(3), 499-534 (2021). doi:10.1007/s11786-021-00515-2 special issue: "Computer Algebra in Scientific Computing 2020 / Issue editors: Matthew England, Francois Boulier, Timur Sadykov, Thomas Sturm", Published by Springer International Publishing AG, Cham (ZG)
Published: 2021

49. Computer Algebra in Scientific Computing 2020

Author: England, Matthew, Boulier, François, Sadykov, Timur, Sturm, Thomas, Coventry University, University of Lille, Plekhanov Russian University of Economics [Moscow] (PRUE), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft, Proof-oriented development of computer-based systems (MOSEL), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Universität des Saarlandes [Saarbrücken], Centre National de la Recherche Scientifique (CNRS), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Saarland University [Saarbrücken]
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2021

50. Standard Conformance-by-Construction with Event-B

Author: Neeraj Kumar Singh, Dominique Méry, Ismail Mendil, Yamine Aït-Ameur, Philippe Palanque, Assistance à la Certification d’Applications DIstribuées et Embarquées (IRIT-ACADIE), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Interactive Critical Systems (IRIT-ICS), Alberto Lluch Lafuente, Anastasia Mavridou, TELECOM Nancy, Université de Lorraine (UL), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), European Research Consortium for Informatics and Mathematics: ERCIM, Working Group on Formal Methods for Industrial Critical Systems, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and ANR-16-CE25-0007,FORMEDICIS,Méthodes formelles pour le développement et l'ingénierie de systèmes interactifs critiques(2016)
Subjects: Computer science, 02 engineering and technology, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], Ontology (information science), Data type, Conformance checking, Domain (software engineering), System model, Safety properties, Event-B and Theories, 0202 electrical engineering, electronic engineering, information engineering, Correctness-by-Construction, Standard conformance, ARINC 661, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Critical Interactive Systems, business.industry, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, [INFO.INFO-IA]Computer Science [cs]/Computer Aided Engineering, Formal system, Systems design, 020201 artificial intelligence & image processing, Software engineering, business
Abstract: International audience; Checking the conformance of a system design to a standard is a central activity in the system engineering life cycle, a fortiori when the concerned system is deemed critical. Standard conformance checking entails ensuring that a system or a model of a system faithfully meets the requirements of a specification of a standard improving the robustness and trustworthiness of the system model. In this paper, we present a formal framework based on the correct-by-construction Event-B method and related theories for formally checking the conformance of a formal system model to a formalised standard specification by construction. This framework facilitates the formalization of standard concepts and rules as an ontology, as well as the formalization of an engineering domain, using an Event-B theory consisting of data types and a collection of operators and properties. Conformance checking is accomplished by annotating the system model with typing conditions. We address an industrial case study borrowed from the aircraft cockpit engineering domain to demonstrate the feasibility and strengths of our approach. The ARINC 661 standard is formalised as an Event-B theory. This theory formally models and annotates the safety-critical real-world application of a weather radar system for certification purposes.
Published: 2021

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

1,682 results on '"Department of Formal Methods (LORIA - FM)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources