Relevant bibliographies by topics / Refinement and proof

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Refinement and proof'

Author: Grafiati
Published: 31 August 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Refinement and proof.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Refinement and proof"

1

Mulder, Ike, and Robbert Krebbers. "Proof Automation for Linearizability in Separation Logic." Proceedings of the ACM on Programming Languages 7, OOPSLA1 (April 6, 2023): 462–91. http://dx.doi.org/10.1145/3586043.

Full text
Abstract:
Recent advances in concurrent separation logic enabled the formal verification of increasingly sophisticated fine-grained ( i.e. , lock-free) concurrent programs. For such programs, the golden standard of correctness is linearizability , which expresses that concurrent executions always behave as some valid sequence of sequential executions. Compositional approaches to linearizability (such as contextual refinement and logical atomicity) make it possible to prove linearizability of whole programs or compound data structures ( e.g. , a ticket lock) using proofs of linearizability of their individual components ( e.g. , a counter). While powerful, these approaches are also laborious—state-of-the-art tools such as Iris, FCSL, and Voila all require a form of interactive proof. This paper develops proof automation for contextual refinement and logical atomicity in Iris. The key ingredient of our proof automation is a collection of proof rules whose application is directed by both the program and the logical state. This gives rise to effective proof search strategies that can prove linearizability of simple examples fully automatically. For more complex examples, we ensure the proof automation cooperates well with interactive proof tactics by minimizing the use of backtracking. We implement our proof automation in Coq by extending and generalizing Diaframe, a proof automation extension for Iris. While the old version (Diaframe 1.0) was limited to ordinary Hoare triples, the new version (Diaframe 2.0) is extensible in its support for program verification styles: our proof search strategies for contextual refinement and logical atomicity are implemented as modules for Diaframe 2.0. We evaluate our proof automation on a set of existing benchmarks and novel proofs, showing that it provides significant reduction of proof work for both approaches to linearizability.
APA, Harvard, Vancouver, ISO, and other styles
2

Song, Youngju, and Dongjae Lee. "Refinement Composition Logic." Proceedings of the ACM on Programming Languages 8, ICFP (August 15, 2024): 573–601. http://dx.doi.org/10.1145/3674645.

Full text
Abstract:
One successful approach to verifying programs is refinement, where one establishes that the implementation (e.g., in C) behaves as specified in its mathematical specification. In this approach, the end result (a whole implementation refines a whole specification) is often established via composing multiple “small” refinements. In this paper, we focus on the task of composing refinements. Our key observation is a novel correspondence between the task of composing refinements and the task of proving entailments in modern separation logic. This correspondence is useful. First, it unlocks tools and abstract constructs developed for separation logic, greatly streamlining the composition proof. Second, it uncovers a fundamentally new verification strategy. We address the key challenge in establishing the correspondence with a novel use of angelic non-determinism. Guided by the correspondence, we develop RCL (Refinement Composition Logic), a logic dedicated to composing refinements. All our results are formalized in Coq.
APA, Harvard, Vancouver, ISO, and other styles
3

Derrick, John, Simon Doherty, Brijesh Dongol, Gerhard Schellhorn, and Heike Wehrheim. "Verifying correctness of persistent concurrent data structures: a sound and complete method." Formal Aspects of Computing 33, no. 4-5 (May 17, 2021): 547–73. http://dx.doi.org/10.1007/s00165-021-00541-8.

Full text
Abstract:
AbstractNon-volatile memory (NVM), aka persistent memory, is a new memory paradigm that preserves its contents even after power loss. The expected ubiquity of NVM has stimulated interest in the design of persistent concurrent data structures, together with associated notions of correctness. In this paper, we present a formal proof technique for durable linearizability, which is a correctness criterion that extends linearizability to handle crashes and recovery in the context ofNVM.Our proofs are based on refinement of Input/Output automata (IOA) representations of concurrent data structures. To this end, we develop a generic procedure for transforming any standard sequential data structure into a durable specification and prove that this transformation is both sound and complete. Since the durable specification only exhibits durably linearizable behaviours, it serves as the abstract specification in our refinement proof. We exemplify our technique on a recently proposed persistentmemory queue that builds on Michael and Scott’s lock-free queue. To support the proofs, we describe an automated translation procedure from code to IOA and a thread-local proof technique for verifying correctness of invariants.
APA, Harvard, Vancouver, ISO, and other styles
4

Bohrer, Brandon, and André Platzer. "Structured Proofs for Adversarial Cyber-Physical Systems." ACM Transactions on Embedded Computing Systems 20, no. 5s (October 31, 2021): 1–26. http://dx.doi.org/10.1145/3477024.

Full text
Abstract:
Many cyber-physical systems (CPS) are safety-critical, so it is important to formally verify them, e.g. in formal logics that show a model’s correctness specification always holds. Constructive Differential Game Logic ( CdGL ) is such a logic for (constructive) hybrid games, including hybrid systems. To overcome undecidability, the user first writes a proof, for which we present a proof-checking tool. We introduce Kaisar , the first language and tool for CdGL proofs, which until now could only be written by hand with a low-level proof calculus. Kaisar’s structured proofs simplify challenging CPS proof tasks, especially by using programming language principles and high-level stateful reasoning. Kaisar exploits CdGL ’s constructivity and refinement relations to build proofs around models of game strategies. The evaluation reproduces and extends existing case studies on 1D and 2D driving. Proof metrics are compared and reported experiences are discussed for the original studies and their reproductions.
APA, Harvard, Vancouver, ISO, and other styles
5

Mylonakis, Nikos. "Proof Assistance for Refinement in Type Theory." Electronic Notes in Theoretical Computer Science 37 (2000): 1–21. http://dx.doi.org/10.1016/s1571-0661(05)01134-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Peng, Jie, Tangliu Wen, Yiguo Yang, and Guoming Huang. "An Event-B Approach to the Development of Fork/Join Parallel Programs." EAI Endorsed Transactions on AI and Robotics 1 (February 18, 2022): 1–6. http://dx.doi.org/10.4108/airo.v1i.16.

Full text
Abstract:
Fork/Join is a simple but effective technique for exploiting the parallelism. When developing a parallel program using Fork/Join, one of the main things is how a large task is decomposed into subtasks whose results can be combined as a final result. In this paper we show how to develop Fork/Join parallel programs through refinement and decomposition. We take Fork/Join style task decomposition as a refinement which we call Fork/Join refinement. Proof obligations of refinement can ensure the correctness of decomposition. For practical application, we provide a refinement pattern for the Fork/Join refinement and extend an atomicity decomposition diagram to illustrate it. Our approach provides a good framework for modeling Fork/Join parallel programs and showing proof obligations of correctness for such programs. We illustrate the approach by applying it on a small case.
APA, Harvard, Vancouver, ISO, and other styles
7

Farissi, Abdallah El. "Simple proof and refinement of Hermite-Hadamard inequality." Journal of Mathematical Inequalities, no. 3 (2010): 365–69. http://dx.doi.org/10.7153/jmi-04-33.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Cansell, Dominique, Dominique Méry, and Cyril Proch. "System-on-chip design by proof-based refinement." International Journal on Software Tools for Technology Transfer 11, no. 3 (March 24, 2009): 217–38. http://dx.doi.org/10.1007/s10009-009-0104-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Gregersen, Simon Oddershede, Alejandro Aguirre, Philipp G. Haselwarter, Joseph Tassarotti, and Lars Birkedal. "Almost-Sure Termination by Guarded Refinement." Proceedings of the ACM on Programming Languages 8, ICFP (August 15, 2024): 203–33. http://dx.doi.org/10.1145/3674632.

Full text
Abstract:
Almost-sure termination is an important correctness property for probabilistic programs, and a number of program logics have been developed for establishing it. However, these logics have mostly been developed for first-order programs written in languages with specific syntactic patterns for looping. In this paper, we consider almost-sure termination for higher-order probabilistic programs with general references. This combination of features allows for recursion and looping to be encoded through a variety of patterns. Therefore, rather than developing proof rules for reasoning about particular recursion patterns, we instead propose an approach based on proving refinement between a higher-order program and a simpler probabilistic model, in such a way that the refinement preserves termination behavior. By proving a refinement, almost-sure termination behavior of the program can then be established by analyzing the simpler model. We present this approach in the form of Caliper, a higher-order separation logic for proving termination-preserving refinements. Caliper uses probabilistic couplings to carry out relational reasoning between a program and a model. To handle the range of recursion patterns found in higher-order programs, Caliper uses guarded recursion, in particular the principle of Löb induction. A technical novelty is that Caliper does not require the use of transfinite step indexing or other technical restrictions found in prior work on guarded recursion for termination-preservation refinement. We demonstrate the flexibility of this approach by proving almost-sure termination of several examples, including first-order loop constructs, a random list generator, treaps, and a sampler for Galton-Watson trees that uses higher-order store. All the results have been mechanized in the Coq proof assistant.
APA, Harvard, Vancouver, ISO, and other styles
10

Mimouni, Sanae, and Mohamed Bouhdadi. "A Mechanized Formal Refinement Proof of Modbus Communication Using Event-B Proof System." International Journal of Intelligent Engineering and Systems 11, no. 4 (August 31, 2018): 97–106. http://dx.doi.org/10.22266/ijies2018.0831.10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Refinement and proof"

1

Pratten, Chris H. "Refinement in a language with procedures and modules." Thesis, University of Southampton, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.243120.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Riviere, Peter. "Génération automatique d’obligations de preuves paramétrée par des théories de domaine dans Event-B : Le cadre de travail EB4EB." Electronic Thesis or Diss., Université de Toulouse (2023-....), 2024. http://www.theses.fr/2024TLSEP052.

Full text
Abstract:
De nos jours, nous sommes entourés de systèmes critiques complexes tels que les microprocesseurs, les trains, les appareils intelligents, les robots, les avions, etc. Ces systèmes sont extrêmement complexes et critiques en termes de sûreté, et doivent donc être vérifiés et validés. L'utilisation de méthodes formelles à états s'est avérée efficace pour concevoir des systèmes complexes. Event-B a joué un rôle clé dans le développement de tels systèmes. Event-B est une méthode formelle de conception de systèmes à états avec une approche correcte par construction, qui met l'accent sur la preuve et le raffinement. Event-B facilite la vérification de propriétés telles que la préservation des invariants, la convergence et le raffinement en générant des obligations de preuve et en permettant de les décharger.Certaines propriétés additionnelles du système, telles que l'absence d'inter-blocage, l'atteignabilité ou encore la vivacité, doivent être explicitement encodées et vérifiées par le concepteur, ou formalisées à l'aide d'une autre méthode formelle. Une telle approche pénalise la réutilisabilité des modèles et des techniques, et peut introduire des erreurs, en particulier dans les systèmes complexes.Pour pallier cela, nous avons introduit un "framework" réflexif EB4EB, formalisé au sein de Event-B. Dans ce cadre, chacun des concepts d'Event-B est formalisé comme un objet de première classe en utilisant la logique du premier ordre (FOL) et la théorie des ensembles. EB4EB permet la manipulation et l'analyse de modèles Event-B, et permet la définition d'extensions afin de réaliser des analyses supplémentaires non intrusives sur des modèles, telles que la validation de propriétés temporelles, l'analyse de la couverture d'un invariant, ou encore l'absence de blocage. Ce framework est réalisé grâce aux théories d'Event-B, qui étendent le langage d'Event-B avec des éléments définis dans des théories, et aussi en formalisant de nouvelles obligations de preuves, qui ne sont pas présentes initialement dans Event-B.De plus, la sémantique opérationnelle d'Event-B (basée sur les traces) a été formalisée, de même qu'un cadre qui sert à garantir la correction des théorèmes définis, y compris les opérateurs et les obligations de preuve. Enfin, le cadre proposé et ses extensions ont été validés dans de multiples études de cas, notamment l'horloge de Lamport, le problème du lecteur/rédacteur, l'algorithme de Peterson, les distributeurs automatiques de billets (DAB), les véhicules autonomes, etc
Nowadays, we are surrounded by complex critical systems such as microprocessors, railways, home appliances, robots, aeroplanes, and so on. These systems are extremely complex and are safety-critical, and they must be verified and validated. The use of state-based formal methods has proven to be effective in designing complex systems. Event-B has played a key role in the development of such systems. Event-B is a formal system design method that is state-based and correct-by-construction, with a focus on proof and refinement. Event-B facilitates verification of properties such as invariant preservation, convergence, and refinement by generating and discharging proof obligations.Additional properties for system verification, such as deadlock-freeness, reachability, and liveness, must be explicitly defined and verified by the designer or formalised using another formal method. Such an approach reduces re-usability and may introduce errors, particularly in complex systems.To tackle these challenges, we introduced the reflexive EB4EB framework in Event-B. In this framework, each Event-B concept is formalised as a first-class object using First Order Logic (FOL) and set theory. This framework allows for the manipulation and analysis of Event-B models, with extensions for additional, non-intrusive analyses such as temporal properties, weak invariants, deadlock freeness, and so on. This is accomplished through Event-B Theories, which extend the Event-B language with the theory's defined elements, and also by formalising and articulating new proof obligations that are not present in traditional Event-B. Furthermore, Event-B's operational semantics (based on traces) have been formalised, along with a framework for guaranteeing the soundness of the defined theorems, including operators and proof obligations. Finally, the proposed framework and its extensions have been validated across multiple case studies, including Lamport's clock case study, read/write processes, the Peterson algorithm, Automated Teller Machine (ATM), autonomous vehicles, and so on
APA, Harvard, Vancouver, ISO, and other styles
3

Ratiu, Diana. "Refinement of Classical Proofs for Program Extraction." Diss., lmu, 2011. http://nbn-resolving.de/urn:nbn:de:bvb:19-135054.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Giorgino, Mathieu. "Inductive representation, proofs and refinement of pointer structures." Toulouse 3, 2013. http://thesesups.ups-tlse.fr/2076/.

Full text
Abstract:
Cette thèse s'intègre dans le domaine général des méthodes formelles qui donnent une sémantique aux programmes pour vérifier formellement des propriétés sur ceux-ci. Sa motivation originale provient d'un besoin de certification des systèmes industriels souvent développés à l'aide de l'Ingénierie Dirigée par les Modèles (IDM) et de langages orientés objets (OO). Pour transformer efficacement des modèles (ou graphes), il est avantageux de les représenter à l'aide de structures de pointeurs, économisant le temps et la mémoire grâce au partage qu'ils permettent. Cependant la vérification de propriétés sur des programmes manipulant des pointeurs est encore complexe. Pour la simplifier, nous proposons de démarrer le développement par une implémentation haut-niveau sous la forme de programmes fonctionnels sur des types de données inductifs facilement vérifiables dans des assistants à la preuve tels que Isabelle/HOL. La représentation des structures de pointeurs est faite à l'aide d'un arbre couvrant contenant des références additionnelles. Ces programmes fonctionnels sont ensuite raffinés si nécessaire vers des programmes impératifs à l'aide de la bibliothèque Imperative_HOL. Ces programmes sont en dernier lieu extraits vers du code Scala (OO). Cette thèse décrit la méthodologie de représentation et de raffinement et fournit des outils pour la manipulation et la preuve de programmes OO dans Isabelle/HOL. L'approche est éprouvée par de nombreux exemples dont notamment l'algorithme de Schorr-Waite et la construction de Diagrammes de Décision Binaires (BDDs)
This thesis stands in the general domain of formal methods that gives semantics to programs to formally prove properties about them. It originally draws its motivation from the need for certification of systems in an industrial context where Model Driven Engineering (MDE) and object-oriented (OO) languages are common. In order to obtain efficient transformations on models (graphs), we can represent them as pointer structures, allowing space and time savings through the sharing of nodes. However verification of properties on programs manipulating pointer structures is still hard. To ease this task, we propose to start the development with a high-level implementation embodied by functional programs manipulating inductive data-structures, that are easily verified in proof assistants such as Isabelle/HOL. Pointer structures are represented by a spanning tree adorned with additional references. These functional programs are then refined - if necessary - to imperative programs thanks to the library Imperative_HOL. These programs are finally extracted to Scala code (OO). This thesis describes this kind of representation and refinement and provides tools to manipulate and prove OO programs in Isabelle/HOL. This approach is put in practice with several examples, and especially with the Schorr-Waite algorithm and the construction of Binary Decision Diagrams (BDDs)
APA, Harvard, Vancouver, ISO, and other styles
5

Graja, Zaineb. "Vérification formelle des systèmes multi-agents auto-adaptatifs." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30105/document.

Full text
Abstract:
Un des défis majeurs pour le développement des Systèmes Multi-Agents (SMA) auto-organisateurs est de garantir la convergence du système vers la fonction globale attendue par un observateur externe et de garantir que les agents sont capables de s'adapter face aux perturbations. Dans la littérature, plusieurs travaux se sont basés sur la simulation et le model-checking pour analyser les SMA auto-organisateurs. La simulation permet aux concepteurs d'expérimenter plusieurs paramètres et de créer certaines heuristiques pour faciliter la conception du système. Le model-checking fournit un support pour découvrir les blocages et les violations de propriétés. Cependant, pour faire face à la complexité de la conception des SMA auto-organisateurs, le concepteur a également besoin de techniques qui prennent en charge non seulement la vérification, mais aussi le processus de développement lui-même. En outre, ces techniques doivent permettre un développement méthodique et faciliter le raisonnement sur divers aspects du comportement du système à différents niveaux d'abstraction. Dans cette thèse, trois contributions essentielles ont été apportées dans le cadre du développement et la vérification formelle des SMA auto-organisateurs: une formalisation à l'aide du langage B-événementiel des concepts clés de ces systèmes en trois niveaux d'abstraction (micro, méso et macro), une expérimentation d'une stratégie de raffinement descendante pour le développement des SMA auto-organisateurs et la proposition d'un processus de raffinement ascendant basé sur des patrons de raffinement
A major challenge for the development of self-organizing MAS is to guarantee the convergence of the system to the overall function expected by an external observer and to ensure that agents are able to adapt to changes. In the literature, several works were based on simulation and model-checking to study self-organizing MAS. The simulation allows designers to experiment various settings and create some heuristics to facilitate the system design. Model checking provides support to discover deadlocks and properties violations. However, to cope with the complexity of self-organizing MAS, the designer also needs techniques that support not only verification, but also the development process itself. Moreover, such techniques should support disciplined development and facilitate reasoning about various aspects of the system behavior at different levels of abstraction. In this thesis, three essential contributions were made in the field of formal development and verification of self-organizing MAS: a formalization with the Event-B language of self-organizing MAS key concepts into three levels of abstraction, an experimentation of a top-down refinement strategy for the development of self-organizing MAS and the definition of a bottom-up refinement process based on refinement patterns
APA, Harvard, Vancouver, ISO, and other styles
6

Kherroubi, Souad. "Un cadre formel pour l'intégration de connaissances du domaine dans la conception des systèmes : application au formalisme Event-B." Thesis, Université de Lorraine, 2018. http://www.theses.fr/2018LORR0230/document.

Full text
Abstract:
Cette thèse vise à définir des techniques pour mieux exploiter les connaissances du domaine dans l’objectif de rendre compte de la réalité de systèmes qualifiés de complexes et critiques. La modélisation est une étape indispensable pour effectuer des vérifications et exprimer des propriétés qu’un système doit satisfaire. La modélisation est une représentation simplificatrice, mais réductionniste de la réalité d’un système. Or, un système complexe ne peut se réduire à un modèle. Un modèle doit s’intégrer dans sa théorie observationnelle pour rendre compte des anomalies qu’il peut y contenir. Notre étude montre clairement que le contexte est la première problématique à traiter car principale source de conflits dans le processus de conception d’un système. L’approche retenue dans cette thèse est celle d’intégrer des connaissances du domaine en associant le système à concevoir à des formalismes déclaratifs qualifiés de descriptifs appelés ontologies. Notre attention est portée au formalisme Event-B dont l’approche correct-par-construction appelée raffinement est le principal mécanisme dans ce formalisme qui permet de faire des preuves sur des représentations abstraites de systèmes pour exprimer/vérifier des propriétés de sûreté et d’invariance. Le premier problème traité concerne la représentation et la modélisation des connaissances du contexte en V&V de modèles. Suite à l’étude des sources de conflits, nous avons établi de nouvelles règles pour une extraction de connaissances liées au contexte par raffinement pour la V&V. Une étude des formalismes de représentation et d’interprétation logiques du contexte a permis de définir un nouveau mécanisme pour mieux structurer les modèles Event-B. Une deuxième étude concerne l’apport des connaissances du domaine pour la V&V. Nous définissons une logique pour le formalisme Event-B avec contraintes du domaine fondées sur les logiques de description, établissons des règles à exploiter pour l’intégration de ces connaissances à des fins de V&V. L’évaluation des propositions faites portent sur des études de cas très complexes telles que les systèmes de vote dont des patrons de conception sont aussi développés dans cette thèse. Nous soulevons des problématiques fondamentales sur la complémentarité que peut avoir l’intégration par raffinement des connaissances du domaine à des modèles en exploitant les raisonnements ontologiques, proposons de définir de nouvelles structures pour une extraction partiellement automatisée
This thesis aims at defining techniques to better exploit the knowledge provided from the domain in order to account for the reality of systems described as complex and critical. Modeling is an essential step in performing verifications and expressing properties that a system must satisfy according to the needs and requirements established in the specifications. Modeling is a representation that simplifies the reality of a system. However, a complex system can not be reduced to a model. A model that represents a system must always fit into its observational theory to account for any anomalies that it may contain. Our study clearly shows that the context is the first issue to deal with as the main source of conflict in the design process of a system. The approach adopted in this thesis is that of integrating knowledge of the domain by associating the system to design with declarative formalisms qualified of descriptive ones that we call ontologies. We pay a particular attention to the Event-B formalism, whose correct-by-construction approach called refinement is the main mechanism at the heart of this formalism, which makes it possible to make proofs on abstract representations of systems for expressing and verifying properties of safety and invariance. The first problem treated is the representation and modeling of contextual knowledge in V&V of models. Following to the study looked at the different sources of conflict, we established new definitions and rules for a refinement context knowledge extraction for Event-B V&V. A study of logical formalisms that represent and interpret the context allowed us to define a new mechanism for better structuring Event-B models. A second study concerns the contribution that domain knowledge can make to the V&V of models. We define a logic for the Event-B formalism with domain constraints based on the description logic, and we define rules to integrate domain knowledge for model V&V. The evaluation of the proposals made deal with very complex case studies such as voting systems whose design patterns are also developed in this thesis. We raise fundamental issues about the complementarity that the integration of domain knowledge can bring to Event-B models by refinement using ontological reasoning, and we propose to define a new structures for a partially automated extraction on both levels, namely the V&V
APA, Harvard, Vancouver, ISO, and other styles
7

Ratiu, Diana [Verfasser], and Helmut [Akademischer Betreuer] Schwichtenberg. "Refinement of Classical Proofs for Program Extraction / Diana Ratiu. Betreuer: Helmut Schwichtenberg." München : Universitätsbibliothek der Ludwig-Maximilians-Universität, 2011. http://d-nb.info/1015734464/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Kherroubi, Souad. "Un cadre formel pour l'intégration de connaissances du domaine dans la conception des systèmes : application au formalisme Event-B." Electronic Thesis or Diss., Université de Lorraine, 2018. http://www.theses.fr/2018LORR0230.

Full text
Abstract:
Cette thèse vise à définir des techniques pour mieux exploiter les connaissances du domaine dans l’objectif de rendre compte de la réalité de systèmes qualifiés de complexes et critiques. La modélisation est une étape indispensable pour effectuer des vérifications et exprimer des propriétés qu’un système doit satisfaire. La modélisation est une représentation simplificatrice, mais réductionniste de la réalité d’un système. Or, un système complexe ne peut se réduire à un modèle. Un modèle doit s’intégrer dans sa théorie observationnelle pour rendre compte des anomalies qu’il peut y contenir. Notre étude montre clairement que le contexte est la première problématique à traiter car principale source de conflits dans le processus de conception d’un système. L’approche retenue dans cette thèse est celle d’intégrer des connaissances du domaine en associant le système à concevoir à des formalismes déclaratifs qualifiés de descriptifs appelés ontologies. Notre attention est portée au formalisme Event-B dont l’approche correct-par-construction appelée raffinement est le principal mécanisme dans ce formalisme qui permet de faire des preuves sur des représentations abstraites de systèmes pour exprimer/vérifier des propriétés de sûreté et d’invariance. Le premier problème traité concerne la représentation et la modélisation des connaissances du contexte en V&V de modèles. Suite à l’étude des sources de conflits, nous avons établi de nouvelles règles pour une extraction de connaissances liées au contexte par raffinement pour la V&V. Une étude des formalismes de représentation et d’interprétation logiques du contexte a permis de définir un nouveau mécanisme pour mieux structurer les modèles Event-B. Une deuxième étude concerne l’apport des connaissances du domaine pour la V&V. Nous définissons une logique pour le formalisme Event-B avec contraintes du domaine fondées sur les logiques de description, établissons des règles à exploiter pour l’intégration de ces connaissances à des fins de V&V. L’évaluation des propositions faites portent sur des études de cas très complexes telles que les systèmes de vote dont des patrons de conception sont aussi développés dans cette thèse. Nous soulevons des problématiques fondamentales sur la complémentarité que peut avoir l’intégration par raffinement des connaissances du domaine à des modèles en exploitant les raisonnements ontologiques, proposons de définir de nouvelles structures pour une extraction partiellement automatisée
This thesis aims at defining techniques to better exploit the knowledge provided from the domain in order to account for the reality of systems described as complex and critical. Modeling is an essential step in performing verifications and expressing properties that a system must satisfy according to the needs and requirements established in the specifications. Modeling is a representation that simplifies the reality of a system. However, a complex system can not be reduced to a model. A model that represents a system must always fit into its observational theory to account for any anomalies that it may contain. Our study clearly shows that the context is the first issue to deal with as the main source of conflict in the design process of a system. The approach adopted in this thesis is that of integrating knowledge of the domain by associating the system to design with declarative formalisms qualified of descriptive ones that we call ontologies. We pay a particular attention to the Event-B formalism, whose correct-by-construction approach called refinement is the main mechanism at the heart of this formalism, which makes it possible to make proofs on abstract representations of systems for expressing and verifying properties of safety and invariance. The first problem treated is the representation and modeling of contextual knowledge in V&V of models. Following to the study looked at the different sources of conflict, we established new definitions and rules for a refinement context knowledge extraction for Event-B V&V. A study of logical formalisms that represent and interpret the context allowed us to define a new mechanism for better structuring Event-B models. A second study concerns the contribution that domain knowledge can make to the V&V of models. We define a logic for the Event-B formalism with domain constraints based on the description logic, and we define rules to integrate domain knowledge for model V&V. The evaluation of the proposals made deal with very complex case studies such as voting systems whose design patterns are also developed in this thesis. We raise fundamental issues about the complementarity that the integration of domain knowledge can bring to Event-B models by refinement using ontological reasoning, and we propose to define a new structures for a partially automated extraction on both levels, namely the V&V
APA, Harvard, Vancouver, ISO, and other styles
9

Ledang, Hung. "Traduction systématique de spécifications." Nancy 2, 2002. http://www.theses.fr/2002NAN22004.

Full text
Abstract:
La dérivation des spécifications UML vers B est considérée comme une approche appropriée afin d'utiliser conjointement UML et B dans un développement unifié, pratique, rigoureux de logiciels. D'une part, cette dérivation permet d'utiliser les spécifications UML comme point de départ pour développer les spécifications B. D'autre part, il est possible d'utiliser les outils supports puissants de B comme AtelierB pour analyser les spécifications B dérivées afin d'identifier les défauts au sein de spécifications UML. Cette thèse s'est concentrée sur la dérivation vers B pour les diagrammes d'interaction (collaboration, séquence), les diagrammes d'état-transition et les diagrammes de cas d'utilisation, qui n'a pas été considérée précédemment. Trois procédures de dérivation pour trois types de diagrammes comportementaux ont été proposées. De plus, les schémas de dérivation des contraintes OCL vers B ont été définis. Ce qui permet de dériver systématiquement vers B non seulement les invariants de classes en OCL, les conditins de gardes (toujours en OCL) au sein des diagrammes d'état-transition mais aussi les spécifications OCL de la forme pré- et postcondition des concepts UML comportementaux comme des opérations UML, des cas d'utilisation et des événements. Nous avons aussi développé un outil de support pour la dérivation d'UML/OCL vers B. En plus des schémas de dérivation d'UML/OCL vers B, nous avons proposé certaines analyses de cohérence, grâce à B et ses outils, au sein de la spécification UML ont. Cette thèse peut être poursuite par l'utilisation des schémas de dérivation sur les études de cas réelles afin d'évaluer leur application. Une autre voie est de définir des schémas de dérivation de B vers UML
The diversion of the specifications UML towards B is considered as an approach suited to use jointly UML and B in a unified, practical, rigorous development of software. On one hand, this diversion allows to use the specifications UML as starting point to develop the specifications B. On the other hand, it is possible to use tools powerful supports(media) of B as AtelierB to analyze the specifications B diverted to identify the defects within specifications UML. This thesis(theory) concentrated on the diversion towards B for the diagrams of interaction (collaboration, sequence), the diagrams of state-transition and the diagrams of case of use, which was not previously considered. Three procedures of diversion for three types of behavioral diagrams were proposed. Furthermore, the plans of diversion of the constraints OCL towards B were defined. Which allows to divert systematically towards B not only the invariants of classes in OCL, the conditins of guards (always in OCL) within the diagrams of state-transition but also the specifications OCL of the pre-form and postcondition from concepts UML behavioral as operations UML, cases of use and from the events. We also developed a tool of support for the diversion of UML / OCL towards B. Besides the plans of diversion of UML / OCL towards B, we proposed certain analyses of coherence, thanks to B and its tools, within the specification UML have. This thesis can be pursuit
APA, Harvard, Vancouver, ISO, and other styles
10

Carvalho, Luís. "Three essays on game theory and bargaining." Doctoral thesis, NSBE - UNL, 2014. http://hdl.handle.net/10362/11851.

Full text
Abstract:
A PhD Dissertation, presented as part of the requirements for the Degree of Doctor of Philosophy from the NOVA - School of Business and Economics
Equilibrium Outcomes of Repeated Two-Person Zero-Sum Games - We consider discounted repeated two-person zero-sum games. We show that even when players have different discount factors (in which case the repeated game is not a zero-sum game), an outcome is subgame perfect if and only if all of its components are Nash equilibria of the stage game. This implies that in all subgame perfect equilibria, each player's payoff is equal to his minmax payoff. In conclusion, the competitive nature of two-player zero-sum games is not altered when the game is repeated.
A Constructive Proof of the Nash Bargaining Solution - We consider the classical axiomatic Nash bargaining framework and propose a constructive proof of its solution. On the first part of this paper we prove Nash’s solution is the result of a maximization problem; on the second part, through the properties of maximand’s indifference curves we derive that it must be equal to xy.
Equilibria and Outcomes in Multiplayer Bargaining - Multiplayer bargaining is a game in which all possible divisions are equilibrium outcomes. This paper presents the classical subgame perfect equilibria strategies and analyses their weak robustness, namely the use of weakly dominated strategies. The paper then develops a refined equilibrium concept, based on trembling hand perfection, in order to overcome such weakness. Concluding that none of the classical equilibrium strategies survives the imposition of the extra robustness and, albeit using more complex strategies, the equilibrium outcomes don't change.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Refinement and proof"

1

1966-, Engelhardt Kai, and Buth Karl-Heinz, eds. Data refinement: Model-oriented proof methods and their comparison. Cambridge, UK: Cambridge University Press, 1998.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Roever, W. P. de. Data refinement: Model-oriented proof methods and their comparison. Cambridge: Cambridge University Press, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Abstraction, Refinement and Proof for Probabilistic Systems. New York: Springer-Verlag, 2005. http://dx.doi.org/10.1007/b138392.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

McIver, Annabelle, and Charles Carroll Morgan. Abstraction, Refinement and Proof for Probabilistic Systems. Springer London, Limited, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

McIver, Annabelle, and Charles Carroll Morgan. Abstraction, Refinement and Proof for Probabilistic Systems. Springer, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Roever, Willem-Paul de, and Kai Engelhardt. Data Refinement: Model-Oriented Proof Methods and Their Comparison. Cambridge University Press, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Roever, Willem-Paul de, and Kai Engelhardt. Data Refinement: Model-Oriented Proof Methods and Their Comparison. Cambridge University Press, 2011.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Abstraction, Refinement and Proof for Probabilistic Systems (Monographs in Computer Science). Springer, 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Woodcock, Jim, and Jim Davies. Using Z: Specification, Refinement, and Proof (Prentice-Hall International Series in Computer Science). Prentice Hall, 1996.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Using Z: Specification, Refinement, and Proof (Prentice-Hall International Series in Computer Science). Prentice Hall, 1996.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Refinement and proof"

1

Fidge, Colin. "Proof Obligations for Real-Time Refinement." In 6th Refinement Workshop, 279–305. London: Springer London, 1994. http://dx.doi.org/10.1007/978-1-4471-3240-0_15.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Lovas, William, and Frank Pfenning. "Refinement Types as Proof Irrelevance." In Lecture Notes in Computer Science, 157–71. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02273-9_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Prebet, Enguerrand, and André Platzer. "Uniform Substitution for Differential Refinement Logic." In Automated Reasoning, 196–215. Cham: Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-63501-4_11.

Full text
Abstract:
AbstractThis paper introduces a uniform substitution calculus for differential refinement logic . The logic extends the differential dynamic logic such that one can simultaneously reason about properties of and relations between hybrid systems. Refinements are useful e.g. for simplifying proofs by relating a concrete hybrid system to an abstract one from which the property can be proved more easily. Uniform substitution is the key to parsimonious prover microkernels. It enables the verbatim use of single axiom formulas instead of axiom schemata with soundness-critical side conditions scattered across the proof calculus. The uniform substitution rule can then be used to instantiate all axioms soundly. Access to differential variables in enables more control over the notion of refinement, which is shown to be decidable on a fragment of hybrid programs.
APA, Harvard, Vancouver, ISO, and other styles
4

Havelund, Klaus, and Natarajan Shankar. "A Refinement Proof for a Garbage Collector." In From Reactive Systems to Cyber-Physical Systems, 73–103. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-31514-6_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Agerholm, Sten, Juan Bicarregui, and Savi Maharaj. "On the Verification of VDM Specification and Refinement with PVS." In Proof in VDM: Case Studies, 157–89. London: Springer London, 1998. http://dx.doi.org/10.1007/978-1-4471-1532-8_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Dross, Claire, and Yannick Moy. "Abstract Software Specifications and Automatic Proof of Refinement." In Reliability, Safety, and Security of Railway Systems. Modelling, Analysis, Verification, and Certification, 215–30. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-33951-1_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Arcaini, Paolo, Angelo Gargantini, and Elvinia Riccobene. "SMT-Based Automatic Proof of ASM Model Refinement." In Software Engineering and Formal Methods, 253–69. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-41591-8_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Nigam, Vivek, Giselle Reis, Samar Rahmouni, and Harald Ruess. "Proof Search and Certificates for Evidential Transactions." In Automated Deduction – CADE 28, 234–51. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-79876-5_14.

Full text
Abstract:
AbstractAttestation logics have been used for specifying systems with policies involving different principals. Cyberlogic is an attestation logic used for the specification of Evidential Transactions (ETs). In such transactions, evidence has to be provided supporting its validity with respect to given policies. For example, visa applicants may be required to demonstrate that they have sufficient funds to visit a foreign country. Such evidence can be expressed as a Cyberlogic proof, possibly combined with non-logical data (e.g., a digitally signed document). A key issue is how to construct and communicate such evidence/proofs. It turns out that attestation modalities are challenging to use established proof-theoretic methods such as focusing. Our first contribution is the refinement of Cyberlogic proof theory with knowledge operators which can be used to represent knowledge bases local to one or more principals. Our second contribution is the identification of an executable fragment of Cyberlogic, called Cyberlogic programs, enabling the specification of ETs. Our third contribution is a sound and complete proof system for Cyberlogic programs enabling proof search similar to search in logic programming. Our final contribution is a proof certificate format for Cyberlogic programs inspired by Foundational Proof Certificates as a means to communicate evidence and check its validity.
APA, Harvard, Vancouver, ISO, and other styles
9

Ishikawa, Fuyuki, Tsutomu Kobayashi, and Shinichi Honiden. "Explicit Exploration of Refinement Design in Proof-Based Approach: Refinement Engineering in Event-B." In Implicit and Explicit Semantics Integration in Proof-Based Developments of Discrete Systems, 309–30. Singapore: Springer Singapore, 2020. http://dx.doi.org/10.1007/978-981-15-5054-6_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Mutluergil, Suha Orhun, and Serdar Tasiran. "A Mechanized Refinement Proof of the Chase-Lev Deque Using a Proof System." In Networked Systems, 280–94. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-46140-3_23.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Refinement and proof"

1

Morgan, Carroll. "Proof rules for probabilistic loops." In Proceedings of the BCS-FACS 7th Refinement Workshop. BCS Learning & Development, 1996. http://dx.doi.org/10.14236/ewic/rw1996.10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Bossard, Antoine, and Keiichi Kaneko. "UCEJ Database Refinement and Applicability Proof." In 2019 IEEE International Symposium on Multimedia (ISM). IEEE, 2019. http://dx.doi.org/10.1109/ism46123.2019.00018.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bezza, Asma, Elkamel Merah, Rabea Ameur-Boulifa, Rohallah Benaboud, and Toufik Messaoud Maarouk. "Formalization and Refinement Proof for Embedded Systems." In 2020 4th International Symposium on Informatics and its Applications (ISIA). IEEE, 2020. http://dx.doi.org/10.1109/isia51297.2020.9416544.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Hart, Thomas E., Kelvin Ku, Arie Gurfinkel, Marsha Chechik, and David Lie. "Augmenting Counterexample-Guided Abstraction Refinement with Proof Templates." In 2008 23rd IEEE/ACM International Conference on Automated Software Engineering. IEEE, 2008. http://dx.doi.org/10.1109/ase.2008.55.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Clark, Tony. "Object-Oriented Refinement and Proof using Behaviour Functions." In Rigorous Object-Oriented Methods 2000. BCS Learning & Development, 2000. http://dx.doi.org/10.14236/ewic/room2000.2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Stankaitis, Paulius, Guillaume Dupont, Neeraj Kumar Singh, Yamine Ait-Ameur, Alexei Iliasov, and Alexander Romanovsky. "Modelling Hybrid Train Speed Controller using Proof and Refinement." In 2019 24th International Conference on Engineering of Complex Computer Systems (ICECCS). IEEE, 2019. http://dx.doi.org/10.1109/iceccs.2019.00019.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Vindum, Simon Friis, and Lars Birkedal. "Contextual refinement of the Michael-Scott queue (proof pearl)." In CPP '21: 10th ACM SIGPLAN International Conference on Certified Programs and Proofs. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3437992.3439930.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Khalafinejad, Saeed, and Seyed-Hassan Mirian-Hosseinabadi. "Derivation of Z functional input/output refinement proof rules." In 2010 International Conference on Electronics and Information Engineering (ICEIE 2010). IEEE, 2010. http://dx.doi.org/10.1109/iceie.2010.5559891.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Pleasant, James C. "Systematic program development and proof: Dromey's method versus top-down refinement." In the 28th annual Southeast regional conference. New York, New York, USA: ACM Press, 1990. http://dx.doi.org/10.1145/98949.99056.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Dupont, G., Y. Ait-Ameur, M. Pantel, and N. K. Singh. "Handling Refinement of Continuous Behaviors: A Proof Based Approach with Event-B." In 2019 International Symposium on Theoretical Aspects of Software Engineering (TASE). IEEE, 2019. http://dx.doi.org/10.1109/tase.2019.00-25.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Refinement and proof"

1

Lehotay, Steven J., and Aviv Amirav. Ultra-Fast Methods and Instrumentation for the Analysis of Hazardous Chemicals in the Food Supply. United States Department of Agriculture, December 2012. http://dx.doi.org/10.32747/2012.7699852.bard.

Full text
Abstract:
Original proposal objectives: Our main original goal was to develop ultra-fast methods and instrumentation for the analysis of hazardous chemicals in the food supply. We proposed to extend the QuEChERS approach to veterinary drugs and other contaminants, and conduct fast and ultra-fast analyses using novel 5MB-MS instrumentation, ideally with real samples. Background to the topic: The international trade of agricultural food products is a $1.2 trill ion annual market and growing. Food safety is essential to human health, and chemical residue limits are legislated nationally and internationally. Analytical testing for residues is needed to conduct risk assessments and regulatory enforcement actions to ensure food safety and environmental health, among other important needs. Current monitoring methods are better than ever, but they are still too time-consuming, laborious, and expensive to meet the broad food testing needs of consumers, government, and industry. As a result, costs are high and only a tiny fraction of the food is tested for a limited number of contaminants. We need affordable, ultra-fast methods that attain high quality results for a wide range of chemicals. Major conclusions, solutions and achievements: This is the third BARD grant shared between Prof. Amirav and Dr. Lehotay since 2000, and continual analytical improvements have been made in terms of speed, sample throughput, chemical scope, ease-of-use, and quality of results with respect to qualitative (screening and identification) and quantitative factors. The QuEChERS sample preparation approach, which was developed in conjunction with the BARD grant in 2002, has grown to currently become the most common pesticide residue method in the world. BARD funding has been instrumental to help Dr. Lehotay make refinements and expand QuEChERS concepts to additional applications, which has led to the commercialization of QuEChERS products by more than 20 companies worldwide. During the past 3 years, QuEChERS has been applied to multiclass, multiresidue analysis of veterinary drug residues in food animals, and it has been validated and implemented by USDA-FSIS. QuEChERS was also modified and validated for faster, easier, and better analysis of traditional and emerging environmental contaminants in food. Meanwhile, Prof. Amirav has commercialized the GC-MS with 5MB technology and other independent inventions, including the ChromatoProbe with Agilent, Bruker, and FUR Systems. A new method was developed for obtaining truly universal pesticide analysis, based on the use of GC-MS with 5MB. This method and instrument enables faster analysis with lower LaDs for extended range of pesticides and hazardous compounds. A new approach and device of Open Probe Fast GC-MS with 5MB was also developed that enable real time screening of limited number of target pesticides. Implications, both scientific and agricultural: We succeeded in achieving significant improvements in the analysis of hazardous chemicals in the food supply, from easy sample preparation approaches, through sample analysis by advanced new types of GC-MS and LCMS techniques, all the way to improved data analysis by lowering LaD and providing greater confidence in chemical identification. As a result, the combination of the QuEChERS approach, new and superior instrumentation, and the novel monitoring methods that were developed will enable vastly reduced time and cost of analysis, increased analytical scope. and a higher monitoring rate. This provides better enforcement, an added impetus for farmers to use good agricultural practices, improved food safety and security, increased trade. and greater consumer confidence in the food supply.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Refinement and proof' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography