Log in

Relevant bibliographies by topics / Refinement and proof / Journal articles

Journal articles on the topic 'Refinement and proof'

To see the other types of publications on this topic, follow the link: 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 top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

Mutluergil, Suha Orhun, and Serdar Tasiran. "A mechanized refinement proof of the Chase–Lev deque using a proof system." Computing 101, no. 1 (July 2, 2018): 59–74. http://dx.doi.org/10.1007/s00607-018-0635-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Buchsbaum, Christian, and Martin U. Schmidt. "Rietveld refinement of a wrong crystal structure." Acta Crystallographica Section B Structural Science 63, no. 6 (November 9, 2007): 926–32. http://dx.doi.org/10.1107/s0108768107050823.

Full text

Abstract:

Rietveld refinements are generally used to confirm crystal structures solved from powder diffraction data. If the Rietveld refinement converges with low R values and with a smooth difference curve, and the structure looks chemically sensible, the resulting structure is generally considered to be close to the correct crystal structure. Here we present a counter example: The Rietveld refinement of the X-ray powder pattern of γ-quinacridone with the crystal structure of β-quinacridone gives quite a smooth difference curve; the resulting crystal structure looks reasonable in terms of molecular conformation, molecular packing and intermolecular hydrogen bonds. However, neither the lattice parameters, the molecular packing nor the conformation of the molecules show any similarity with the actual structure, which was determined from single-crystal data. This example shows that a successful Rietveld refinement is not always final proof of the correctness of a crystal structure; in special cases the resulting crystal structure may still be wrong.

APA, Harvard, Vancouver, ISO, and other styles

13

el Mimouni, Sanae, and Mohamed Bouhdadi. "Event Based Formalization of Communication Properties for an E-Commerce Protocol: An Event-B Approach." International Journal of Engineering Research in Africa 37 (August 2018): 78–90. http://dx.doi.org/10.4028/www.scientific.net/jera.37.78.

Full text

Abstract:

The objective of this paper aims at modeling and analysis of communication properties of an E-commerce protocol with the Event-B language. NetBill protocol is developed for selling and buying of information and goods through the Internet. In this approach, we have used Event-B as proof-based development method which integrates proof techniques for writing specifications and building the model systematically using refinement, the key point is to start with a very abstract model of the system under development. Step by step details are added to this first model by building a series of more concrete ones. This strategy eases the proof of the correctness of requirements because only a small number of proof obligations are generated at each step. The aims are constructing a model with a clear and accurate formulation of the communication protocol properties and discharge of all proof obligations. The outcome of this procedure was that we achieved a very high degree of automatic proof. We reached a good degree of automatic proof. All interactive proofs involved a small number of steps and were straightforward to reach.

APA, Harvard, Vancouver, ISO, and other styles

14

Luo, Zhaohui. "Program specification and data refinement in type theory." Mathematical Structures in Computer Science 3, no. 3 (September 1993): 333–63. http://dx.doi.org/10.1017/s0960129500000256.

Full text

Abstract:

The study of type theory may offer a uniform language for modular programming, structured specification and logical reasoning. We develop an approach to program specification and data refinement in a type theory with a strong logical power and nice structural mechanisms to show that it provides an adequate formalism for modular development of programs and specifications. Specification of abstract data types is considered, and a notion of abstract implementation between specifications is defined in the type theory and studied as a basis for correct and modular development of programs by stepwise refinement. The higher-order structural mechanisms in the type theory provide useful and flexible tools (specification operations and parameterized specifications) for modular design and structured specification. Refinement maps (programs and design decisions) and proofs of implementation correctness can be developed by means of the existing proof development systems based on type theories.

APA, Harvard, Vancouver, ISO, and other styles

15

Méry, Dominique, and Neeraj Kumar Singh. "Formal Specification of Medical Systems by Proof-Based Refinement." ACM Transactions on Embedded Computing Systems 12, no. 1 (January 2013): 1–25. http://dx.doi.org/10.1145/2406336.2406351.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Cimatti, Alessandro, and Stefano Tonetta. "Contracts-refinement proof system for component-based embedded systems." Science of Computer Programming 97 (January 2015): 333–48. http://dx.doi.org/10.1016/j.scico.2014.06.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Dümbgen, Lutz. "A simple proof and refinement of Wielandt's eigenvalue inequality." Statistics & Probability Letters 25, no. 2 (November 1995): 113–15. http://dx.doi.org/10.1016/0167-7152(94)00212-q.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

BANACH, RICHARD, and CZESŁAW JESKE. "Retrenchment and refinement interworking: the tower theorems." Mathematical Structures in Computer Science 25, no. 1 (December 2, 2014): 135–202. http://dx.doi.org/10.1017/s0960129514000061.

Full text

Abstract:

Retrenchment is a flexible model evolution formalism that compensates for the limitations imposed by specific formulations of refinement. Its refinement-like proof obligations feature additional predicates for accommodating design data describing the model change. The best results are obtained when refinement and retrenchment cooperate, the paradigmatic scheme for this being the commuting square or tower, in which ‘horizontal retrenchment rungs’ commute with ‘vertical refinement columns’ to navigate through a much more extensive design space than permitted by refinement alone. In practice, the navigation is accomplished through ‘square completion’ constructions, and we present and prove a full suite of square completion theorems.

APA, Harvard, Vancouver, ISO, and other styles

19

GORRIERI, ROBERTO, and UGO MONTANARI. "TOWARDS HIERARCHICAL DESCRIPTION OF SYSTEMS: A PROOF SYSTEM FOR STRONG PREFIXING." International Journal of Foundations of Computer Science 01, no. 03 (September 1990): 277–93. http://dx.doi.org/10.1142/s0129054190000205.

Full text

Abstract:

The problem of relating system descriptions at different levels of abstraction is addressed in the context of process description languages. As a case study, we introduce two nondeterministic languages. The latter is a simple extension of the former and is obtained by adding to its signature an operator of strong prefixing for making atomic the execution of a sequence of actions. The two languages are intended to be a specification and an implementation language, respectively. To directly relate them, we introduce a mapping, called atomic action refinement, from actions of the former to atomic sequences (i.e. sequences of actions built with strong prefixing) of the latter, which can be homomorphically extended to become a mapping among process terms of the two languages. A notion of implementation, based on a sort of bisimulation (parametric with respect to an atomic action refinement), relates processes of the two languages. Given a specification process P and an atomic action refinement ρ, the refined process ρ(P) is proved to be an implementation of P. Moreover, two complete proof systems for the two languages (and thus also for the operator of strong prefixing) are presented and proved consistent with respect to refinement: if P and Q are congruent processes of the specification language, then ρ(P) and ρ(Q) are congruent, too.

APA, Harvard, Vancouver, ISO, and other styles

20

Qiu, Longfei, Yoonseung Kim, Ji-Yong Shin, Jieung Kim, Wolf Honoré, and Zhong Shao. "LiDO: Linearizable Byzantine Distributed Objects with Refinement-Based Liveness Proofs." Proceedings of the ACM on Programming Languages 8, PLDI (June 20, 2024): 1140–64. http://dx.doi.org/10.1145/3656423.

Full text

Abstract:

Byzantine fault-tolerant state machine replication (SMR) protocols, such as PBFT, HotStuff, and Jolteon, are essential for modern blockchain technologies. However, they are challenging to implement correctly because they have to deal with any unexpected message from byzantine peers and ensure safety and liveness at all times. Many formal frameworks have been developed to verify the safety of SMR implementations, but there is still a gap in the verification of their liveness. Existing liveness proofs are either limited to the network level or do not cover popular partially synchronous protocols. We introduce LiDO, a consensus model that enables the verification of both safety and liveness of implementations through refinement. We observe that current consensus models cannot handle liveness because they do not include a pacemaker state. We show that by adding a pacemaker state to the LiDO model, we can express the liveness properties of SMR protocols as a few safety properties that can be easily verified by refinement proofs. Based on our LiDO model, we provide mechanized safety and liveness proofs for both unpipelined and pipelined Jolteon in Coq. This is the first mechanized liveness proof for a byzantine consensus protocol with non-trivial optimizations such as pipelining.

APA, Harvard, Vancouver, ISO, and other styles

21

Lai, Tri. "Proof of a refinement of Blum’s conjecture on hexagonal dungeons." Discrete Mathematics 340, no. 7 (July 2017): 1617–32. http://dx.doi.org/10.1016/j.disc.2017.03.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Bejenaru, Ioan. "The multilinear restriction estimate: a short proof and a refinement." Mathematical Research Letters 24, no. 6 (2017): 1585–603. http://dx.doi.org/10.4310/mrl.2017.v24.n6.a1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Choppy, Christine, Micaela Mayero, and Laure Petrucci. "Coloured Petri net refinement specification and correctness proof with Coq." Innovations in Systems and Software Engineering 6, no. 3 (April 23, 2010): 195–202. http://dx.doi.org/10.1007/s11334-010-0131-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Atiya, D., S. King, and J. C. P. Woodcock. "Simpler Reasoning About System Properties: a Proof-by-Refinement Technique." Electronic Notes in Theoretical Computer Science 137, no. 2 (July 2005): 5–22. http://dx.doi.org/10.1016/j.entcs.2005.04.022.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Simić, Danijela. "Using Small -Step Refinement for Algorithm Verification in Computer Science Education." International Journal for Technology in Mathematics Education 22, no. 4 (December 1, 2015): 155–62. http://dx.doi.org/10.1564/tme_v22.4.03.

Full text

Abstract:

Stepwise program refinement techniques can be used to simplify program verification. Programs are better understood since their main properties are clearly stated, and verification of rather complex algorithms is reduced to proving simple statements connecting successive program specifications. Additionally, it is easy to analyse similar algorithms and to compare their properties within a single formalization. Usually, formal analysis is not done in the educational setting due to complexity of verification and a lack of tools and procedures to make comparison easy. Verification of an algorithm should not only give a correctness proof, but also better understanding of an algorithm. If the verification is based on a small step program refinement, it can become simple enough to be demonstrated within the university-level computer science curriculum. In this paper we demonstrate this and give a formal analysis of two well- known algorithms (Selection Sort and Heap Sort) using the proof assistant Isabelle/HOL and program refinement techniques.

APA, Harvard, Vancouver, ISO, and other styles

26

Sándor, József. "On certain inequalities for the prime counting function." Notes on Number Theory and Discrete Mathematics 27, no. 4 (December 2021): 149–53. http://dx.doi.org/10.7546/nntdm.2021.27.4.149-153.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Cohen, Stephen D., and A. M. W. Glass. "Composites of translations and odd rational powers act freely." Bulletin of the Australian Mathematical Society 51, no. 1 (February 1995): 73–81. http://dx.doi.org/10.1017/s0004972700013903.

Full text

Abstract:

It is shown that no non-trivial composition of translations x ↦ x + a and odd rational powers x ↦p/q, where p,q are odd co-prime integers, positive or negative with p/q≠±, acts like the identity on a field of characteristic zero. This extends a theorem of Adeleke, Glass, and Morley in which only odd positive rational powers were considered. Moreover, the nature of the proof itself (by field theory) is a simplification and natural refinement of previous proofs. It has applications in other settings.

APA, Harvard, Vancouver, ISO, and other styles

28

Farzan, Azadeh, Dominik Klumpp, and Andreas Podelski. "Stratified Commutativity in Verification Algorithms for Concurrent Programs." Proceedings of the ACM on Programming Languages 7, POPL (January 9, 2023): 1426–53. http://dx.doi.org/10.1145/3571242.

Full text

Abstract:

The importance of exploiting commutativity relations in verification algorithms for concurrent programs is well-known. They can help simplify the proof and improve the time and space efficiency. This paper studies commutativity relations as a first-class object in the setting of verification algorithms for concurrent programs. A first contribution is a general framework for abstract commutativity relations . We introduce a general soundness condition for commutativity relations, and present a method to automatically derive sound abstract commutativity relations from a given proof. The method can be used in a verification algorithm based on abstraction refinement to compute a new commutativity relation in each iteration of the abstraction refinement loop. A second result is a general proof rule that allows one to combine multiple commutativity relations, with incomparable power, in a stratified way that preserves soundness and allows one to profit from the full power of the combined relations. We present an algorithm for the stratified proof rule that performs an optimal combination (in a sense made formal), enabling usage of stratified commutativity in algorithmic verification. We empirically evaluate the impact of abstract commutativity and stratified combination of commutativity relations on verification algorithms for concurrent programs.

APA, Harvard, Vancouver, ISO, and other styles

29

Komlós, János, and Endre Szemerédi. "Topological cliques in graphs II." Combinatorics, Probability and Computing 5, no. 1 (March 1996): 79–90. http://dx.doi.org/10.1017/s096354830000184x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Li, Jie, Kai Hu, Jian Zhu, Jean-Paul Bodeveix, and Yafei Ye. "Formal Modelling of PBFT Consensus Algorithm in Event-B." Wireless Communications and Mobile Computing 2022 (October 14, 2022): 1–17. http://dx.doi.org/10.1155/2022/4467917.

Full text

Abstract:

The practical Byzantine Fault Tolerance (PBFT) is a classical consensus algorithm that has been widely applied in an alliance blockchain system to make all nodes agree to certain transactions under the assumption that the proportion of Byzantine nodes is no more than 1/3. It is prevalent due to its performance, simplicity, and claimed correctness. However, any vulnerability of the consensus algorithm can lead to a significant loss in finance because no one can change the transaction results after execution. This paper proposes a formal development method of the PBFT algorithm by horizontal refinement in Event-B, which allows us to manage the complexity of the proof process by factoring the proof of correctness into several refinement steps. During the development of PBFT, we have specified the core mechanism like parameterized message types, primary node change, and water-mark interval. Furthermore, we present a mechanical verification of the safety and liveness properties of the model in Rodin, which can be partially and widely used to check the blockchain consensus algorithm vulnerability using a refinement tree of algorithms.

APA, Harvard, Vancouver, ISO, and other styles

31

Bobkov, Sergey G., Gennadiy P. Chistyakov, and Friedrich Götze. "Richter’s local limit theorem, its refinement, and related results*." Lithuanian Mathematical Journal 63, no. 2 (April 2023): 138–60. http://dx.doi.org/10.1007/s10986-023-09598-9.

Full text

Abstract:

We give a detailed exposition of the proof of Richter’s local limit theorem in a refined form and establish the stability of the remainder term in this theorem under small perturbations of the underlying distribution (including smoothing).We also discuss related quantitative bounds for characteristic functions and Laplace transforms.

APA, Harvard, Vancouver, ISO, and other styles

32

Sándor, József. "On an Arithmetic Inequality." Analele Universitatii "Ovidius" Constanta - Seria Matematica 22, no. 1 (December 10, 2014): 257–61. http://dx.doi.org/10.2478/auom-2014-0021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Grimmett, Geoffrey R., Tobias J. Osborne, and Petra F. Scudo. "Bounded Entanglement Entropy in the Quantum Ising Model." Journal of Statistical Physics 178, no. 1 (December 2, 2019): 281–96. http://dx.doi.org/10.1007/s10955-019-02432-y.

Full text

Abstract:

AbstractA rigorous proof is presented of the boundedness of the entanglement entropy of a block of spins for the ground state of the one-dimensional quantum Ising model with sufficiently strong transverse field. This is proved by a refinement of the stochastic geometric arguments in the earlier work by Grimmett et al. (J Stat Phys 131:305–339, 2008). The proof utilises a transformation to a model of classical probability called the continuum random-cluster model. Our method of proof is fairly robust, and applies also to certain disordered systems.

APA, Harvard, Vancouver, ISO, and other styles

34

Kawamata, Fuga, Hiroshi Unno, Taro Sekiyama, and Tachio Terauchi. "Answer Refinement Modification: Refinement Type System for Algebraic Effects and Handlers." Proceedings of the ACM on Programming Languages 8, POPL (January 5, 2024): 115–47. http://dx.doi.org/10.1145/3633280.

Full text

Abstract:

Algebraic effects and handlers are a mechanism to structure programs with computational effects in a modular way. They are recently gaining popularity and being adopted in practical languages, such as OCaml. Meanwhile, there has been substantial progress in program verification via refinement type systems . While a variety of refinement type systems have been proposed, thus far there has not been a satisfactory refinement type system for algebraic effects and handlers. In this paper, we fill the void by proposing a novel refinement type system for languages with algebraic effects and handlers. The expressivity and usefulness of algebraic effects and handlers come from their ability to manipulate delimited continuations , but delimited continuations also complicate programs’ control flow and make their verification harder. To address the complexity, we introduce a novel concept that we call answer refinement modification (ARM for short), which allows the refinement type system to precisely track what effects occur and in what order when a program is executed, and reflect such information as modifications to the refinements in the types of delimited continuations. We formalize our type system that supports ARM (as well as answer type modification, or ATM) and prove its soundness. Additionally, as a proof of concept, we have extended the refinement type system to a subset of OCaml 5 which comes with a built-in support for effect handlers, implemented a type checking and inference algorithm for the extension, and evaluated it on a number of benchmark programs that use algebraic effects and handlers. The evaluation demonstrates that ARM is conceptually simple and practically useful. Finally, a natural alternative to directly reasoning about a program with delimited continuations is to apply a continuation passing style (CPS) transformation that transforms the program to a pure program without delimited continuations. We investigate this alternative in the paper, and show that the approach is indeed possible by proposing a novel CPS transformation for algebraic effects and handlers that enjoys bidirectional (refinement-)type-preservation. We show that there are pros and cons with this approach, namely, while one can use an existing refinement type checking and inference algorithm that can only (directly) handle pure programs, there are issues such as needing type annotations in source programs and making the inferred types less informative to a user.

APA, Harvard, Vancouver, ISO, and other styles

35

Sumners, Rob. "Proof Reduction of Fair Stuttering Refinement of Asynchronous Systems and Applications." Electronic Proceedings in Theoretical Computer Science 249 (May 2, 2017): 78–94. http://dx.doi.org/10.4204/eptcs.249.6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Dousse, Jehanne. "A combinatorial proof and refinement of a partition identity of Siladić." European Journal of Combinatorics 39 (July 2014): 223–32. http://dx.doi.org/10.1016/j.ejc.2014.01.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Andriamiarina, Bruno, Dominique Méry, and Kumar Singh. "Revisiting snapshot algorithms by refinement-based techniques." Computer Science and Information Systems 11, no. 1 (2014): 251–70. http://dx.doi.org/10.2298/csis130122007a.

Full text

Abstract:

The snapshot problem addresses a collection of important algorithmic issues related to distributed computations, which are used for debugging or recovering distributed programs. Among existing solutions, Chandy and Lamport have proposed a simple distributed algorithm. In this paper, we explore the correct-byconstruction process to formalize the snapshot algorithms in distributed system. The formalization process is based on a modeling language Event B, which supports a refinement-based incremental development using RODIN platform. These refinement-based techniques help to derive correct distributed algorithms. Moreover, we demonstrate how other distributed algorithms can be revisited. A consequence is to provide a fully mechanized proof of the resulting distributed algorithms.

APA, Harvard, Vancouver, ISO, and other styles

38

Pulte, Christopher, Dhruv C. Makwana, Thomas Sewell, Kayvan Memarian, Peter Sewell, and Neel Krishnaswami. "CN: Verifying Systems C Code with Separation-Logic Refinement Types." Proceedings of the ACM on Programming Languages 7, POPL (January 9, 2023): 1–32. http://dx.doi.org/10.1145/3571194.

Full text

Abstract:

Despite significant progress in the verification of hypervisors, operating systems, and compilers, and in verification tooling, there exists a wide gap between the approaches used in verification projects and conventional development of systems software. We see two main challenges in bringing these closer together: verification handling the complexity of code and semantics of conventional systems software, and verification usability. We describe an experiment in verification tool design aimed at addressing some aspects of both: we design and implement CN, a separation-logic refinement type system for C systems software, aimed at predictable proof automation, based on a realistic semantics of ISO C. CN reduces refinement typing to decidable propositional logic reasoning, uses first-class resources to support pointer aliasing and pointer arithmetic, features resource inference for iterated separating conjunction, and uses a novel syntactic restriction of ghost variables in specifications to guarantee their successful inference. We implement CN and formalise key aspects of the type system, including a soundness proof of type checking. To demonstrate the usability of CN we use it to verify a substantial component of Google's pKVM hypervisor for Android.

APA, Harvard, Vancouver, ISO, and other styles

39

Kashio, Tomokazu. "Fermat curves and a refinement of the reciprocity law on cyclotomic units." Journal für die reine und angewandte Mathematik (Crelles Journal) 2018, no. 741 (August 1, 2018): 255–73. http://dx.doi.org/10.1515/crelle-2015-0081.

Full text

Abstract:

Abstract We define a “period-ring-valued beta function” and give a reciprocity law on its special values. The proof is based on some results of Rohrlich and Coleman concerning Fermat curves. We also have the following application. Stark’s conjecture implies that the exponentials of the derivatives at s=0 of partial zeta functions are algebraic numbers which satisfy a reciprocity law under certain conditions. It follows from Euler’s formulas and properties of cyclotomic units when the base field is the rational number field. In this paper, we provide an alternative proof of a weaker result by using the reciprocity law on the period-ring-valued beta function. In other words, the reciprocity law given in this paper is a refinement of the reciprocity law on cyclotomic units.

APA, Harvard, Vancouver, ISO, and other styles

40

Gäher, Lennard, Michael Sammler, Ralf Jung, Robbert Krebbers, and Derek Dreyer. "RefinedRust: A Type System for High-Assurance Verification of Rust Programs." Proceedings of the ACM on Programming Languages 8, PLDI (June 20, 2024): 1115–39. http://dx.doi.org/10.1145/3656422.

Full text

Abstract:

Rust is a modern systems programming language whose ownership-based type system statically guarantees memory safety, making it particularly well-suited to the domain of safety-critical systems. In recent years, a wellspring of automated deductive verification tools have emerged for establishing functional correctness of Rust code. However, none of the previous tools produce foundational proofs (machine-checkable in a general-purpose proof assistant), and all of them are restricted to the safe fragment of Rust. This is a problem because the vast majority of Rust programs make use of unsafe code at critical points, such as in the implementation of widely-used APIs. We propose RefinedRust, a refinement type system—proven sound in the Coq proof assistant—with the goal of establishing foundational semi-automated functional correctness verification of both safe and unsafe Rust code. We have developed a prototype verification tool implementing RefinedRust. Our tool translates Rust code (with user annotations) into a model of Rust embedded in Coq, and then checks its adherence to the RefinedRust type system using separation logic automation in Coq. All proofs generated by RefinedRust are checked by the Coq proof assistant, so the automation and type system do not have to be trusted. We evaluate the effectiveness of RefinedRust by verifying a variant of Rust’s Vec implementation that involves intricate reasoning about unsafe pointer-manipulating code.

APA, Harvard, Vancouver, ISO, and other styles

41

Jacobs, Philipp, Andreas Houben, Werner Schweika, Andrei L. Tchougréeff, and Richard Dronskowski. "A Rietveld refinement method for angular- and wavelength-dispersive neutron time-of-flight powder diffraction data." Journal of Applied Crystallography 48, no. 6 (October 13, 2015): 1627–36. http://dx.doi.org/10.1107/s1600576715016520.

Full text

Abstract:

This paper introduces a two-dimensional extension of the well established Rietveld refinement method for modeling neutron time-of-flight powder diffraction data. The novel approach takes into account the variation of two parameters, diffraction angle 2θ and wavelength λ, to optimally adapt to the varying resolution function in diffraction experiments. By doing so, the refinement against angular- and wavelength-dispersive data gets rid of common data-reduction steps and also avoids the loss of high-resolution information typically introduced by integration. In a case study using a numerically simulated diffraction pattern of Rh0.81Fe3.19N taking into account the layout of the future POWTEX instrument, the profile function as parameterized in 2θ and λ is extracted. As a proof-of-concept, the resulting instrument parameterization is then utilized to perform a typical refinement of the angular- and wavelength-dispersive diffraction pattern of CuNCN, yielding excellent residuals within feasible computational efforts. Another proof-of-concept is carried out by applying the same approach to a real neutron diffraction data set of CuNCN obtained from the POWGEN instrument at the Spallation Neutron Source in Oak Ridge. The paper highlights the general importance of the novel approach for data analysis at neutron time-of-flight diffractometers and its possible inclusion within existing Rietveld software packages.

APA, Harvard, Vancouver, ISO, and other styles

42

Bessenrodt, Christine. "A Combinatorial Proof of a Refinement of the Andrews—Olsson Partition Identity." European Journal of Combinatorics 12, no. 4 (July 1991): 271–76. http://dx.doi.org/10.1016/s0195-6698(13)80109-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Han, Guo-Niu. "The Nekrasov-Okounkov hook length formula: refinement, elementary proof, extension and applications." Annales de l’institut Fourier 60, no. 1 (2010): 1–29. http://dx.doi.org/10.5802/aif.2515.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

MELLIÈS, PAUL-ANDRÉ, and NOAM ZEILBERGER. "An Isbell duality theorem for type refinement systems." Mathematical Structures in Computer Science 28, no. 6 (March 20, 2017): 736–74. http://dx.doi.org/10.1017/s0960129517000068.

Full text

Abstract:

Any refinement system (= functor) has a fully faithful representation in the refinement system of presheaves, by interpreting types as relative slice categories, and refinement types as presheaves over those categories. Motivated by an analogy between side effects in programming andcontext effectsin linear logic, we study logical aspects of this ‘positive’ (covariant) representation, as well as of an associated ‘negative’ (contravariant) representation. We establish several preservation properties for these representations, including a generalization of Day's embedding theorem for monoidal closed categories. Then, we establish that the positive and negative representations satisfy an Isbell-style duality. As corollaries, we derive two different formulas for the positive representation of a pushforward (inspired by the classical negative translations of proof theory), which express it either as the dual of a pullback of a dual or as the double dual of a pushforward. Besides explaining how these constructions on refinement systems generalize familiar category-theoretic ones (by viewing categories as special refinement systems), our main running examples involve representations of Hoare logic and linear sequent calculus.

APA, Harvard, Vancouver, ISO, and other styles

45

Boyle, Mike, and Scott Schmieding. "Strong shift equivalence and algebraic K-theory." Journal für die reine und angewandte Mathematik (Crelles Journal) 2019, no. 752 (July 1, 2019): 63–104. http://dx.doi.org/10.1515/crelle-2016-0056.

Full text

Abstract:

Abstract For a semiring \mathcal{R} , the relations of shift equivalence over \mathcal{R} ( \textup{SE-}\mathcal{R} ) and strong shift equivalence over \mathcal{R} ( \textup{SSE-}\mathcal{R} ) are natural equivalence relations on square matrices over \mathcal{R} , important for symbolic dynamics. When \mathcal{R} is a ring, we prove that the refinement of \textup{SE-}\mathcal{R} by \textup{SSE-}\mathcal{R} , in the \textup{SE-}\mathcal{R} class of a matrix A, is classified by the quotient NK_{1}(\mathcal{R})/E(A,\mathcal{R}) of the algebraic K-theory group NK_{1}(\mathcal{R}) . Here, E(A,\mathcal{R}) is a certain stabilizer group, which we prove must vanish if A is nilpotent or invertible. For this, we first show for any square matrix A over \mathcal{R} that the refinement of its \textup{SE-}\mathcal{R} class into \textup{SSE-}\mathcal{R} classes corresponds precisely to the refinement of the \mathrm{GL}(\mathcal{R}[t]) equivalence class of I-tA into \mathrm{El}(\mathcal{R}[t]) equivalence classes. We then show this refinement is in bijective correspondence with NK_{1}(\mathcal{R})/E(A,\mathcal{R}) . For a general ring \mathcal{R} and A invertible, the proof that E(A,\mathcal{R}) is trivial rests on a theorem of Neeman and Ranicki on the K-theory of noncommutative localizations. For \mathcal{R} commutative, we show \cup_{A}E(A,\mathcal{R})=NSK_{1}(\mathcal{R}) ; the proof rests on Nenashev’s presentation of K_{1} of an exact category.

APA, Harvard, Vancouver, ISO, and other styles

46

Sababheh, Mohammad, Hamid Moradi, Ibrahim Gümüş, and Shigeru Furuichi. "A note on Kantorovich and Ando inequalities." Filomat 37, no. 13 (2023): 4171–83. http://dx.doi.org/10.2298/fil2313171s.

Full text

Abstract:

The main goal of this exposition is to present further analysis of the Kantorovich and Ando operator inequalities. In particular, a new proof of Ando?s inequality is given, a new non-trivial refinement of Kantorovich inequality is shown, and some equivalent forms of the Kantorovich inequality are presented with a Minkowski-type application.

APA, Harvard, Vancouver, ISO, and other styles

47

Zafar, Nazir Ahmad, Ajmal Hussain, and Amir Ali. "Refinement in Formal Proof of Equivalence in Morphisms over Strongly Connected Algebraic Automata." Journal of Software Engineering and Applications 02, no. 02 (2009): 77–85. http://dx.doi.org/10.4236/jsea.2009.22012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Sun, Chia-Hung, and Fu-Chuan Lai. "Hotelling was right with decreasing returns to scale and a coalition-proof refinement." Annals of Regional Science 50, no. 3 (August 25, 2012): 953–71. http://dx.doi.org/10.1007/s00168-012-0528-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Ge, Hua-feng. "New Sharp Bounds for the Bernoulli Numbers and Refinement of Becker-Stark Inequalities." Journal of Applied Mathematics 2012 (2012): 1–7. http://dx.doi.org/10.1155/2012/137507.

Full text

Abstract:

We obtain new sharp bounds for the Bernoulli numbers:2(2n)!/(π2n(22n−1))<|B2n|≤(2(22k−1)/22k)ζ(2k)(2n)!/(π2n(22n−1)),n=k,k+1,…, k∈N+, and establish sharpening of Papenfuss's inequalities, the refinements of Becker-Stark, and Steckin's inequalities. Finally, we show a new simple proof of Ruehr-Shafer inequality.

APA, Harvard, Vancouver, ISO, and other styles

50

FISCHLER, STÉPHANE. "SHIDLOVSKY’S MULTIPLICITY ESTIMATE AND IRRATIONALITY OF ZETA VALUES." Journal of the Australian Mathematical Society 105, no. 2 (June 18, 2018): 145–72. http://dx.doi.org/10.1017/s1446788717000386.

Full text

Abstract:

In this paper we follow the approach of Bertrand–Beukers (and of Bertrand’s later work), based on differential Galois theory, to prove a very general version of Shidlovsky’s lemma that applies to Padé-approximation problems at several points, both at functional and numerical levels (that is, before and after evaluating at a specific point). This allows us to obtain a new proof of the Ball–Rivoal theorem on irrationality of infinitely many values of the Riemann zeta function at odd integers, inspired by the proof of the Siegel–Shidlovsky theorem on values of $E$-functions: Shidlovsky’s lemma is used to replace Nesterenko’s linear independence criterion with Siegel’s, so that no lower bound is needed on the linear forms in zeta values. The same strategy provides a new proof, and a refinement, of Nishimoto’s theorem on values of $L$-functions of Dirichlet characters.

APA, Harvard, Vancouver, ISO, and other styles

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!