Log in

Relevant bibliographies by topics / Constrained horn clauses

Contents

Journal articles

Academic literature on the topic 'Constrained horn clauses'

Author: Grafiati

Published: 6 September 2023

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 'Constrained horn clauses.'

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 "Constrained horn clauses"

1

DE ANGELIS, EMANUELE, FABIO FIORAVANTI, ALBERTO PETTOROSSI, and MAURIZIO PROIETTI. "Proving correctness of imperative programs by linearizing constrained Horn clauses." Theory and Practice of Logic Programming 15, no. 4-5 (2015): 635–50. http://dx.doi.org/10.1017/s1471068415000289.

Full text

Abstract:

AbstractWe present a method for verifying the correctness of imperative programs which is based on the automated transformation of their specifications. Given a program prog, we consider a partial correctness specification of the form {ϕ}, prog {ψ}, where the assertions ϕ and ψ are predicates defined by a set Spec of possibly recursive Horn clauses with linear arithmetic (LA) constraints in their premise (also called constrained Horn clauses). The verification method consists in constructing a set PC of constrained Horn clauses whose satisfiability implies that {ϕ}, prog, {ψ} is valid. We high

APA, Harvard, Vancouver, ISO, and other styles

2

KAFLE, BISHOKSAN, JOHN P. GALLAGHER, and PIERRE GANTY. "Tree dimension in verification of constrained Horn clauses." Theory and Practice of Logic Programming 18, no. 2 (2018): 224–51. http://dx.doi.org/10.1017/s1471068418000030.

Full text

Abstract:

AbstractIn this paper, we show how the notion of tree dimension can be used in the verification of constrained Horn clauses (CHCs). The dimension of a tree is a numerical measure of its branching complexity and the concept here applies to Horn clause derivation trees. Derivation trees of dimension zero correspond to derivations using linear CHCs, while trees of higher dimension arise from derivations using non-linear CHCs. We show how to instrument CHCs predicates with an extra argument for the dimension, allowing a CHC verifier to reason about bounds on the dimension of derivations. Given a s

APA, Harvard, Vancouver, ISO, and other styles

3

DE ANGELIS, EMANUELE, FABIO FIORAVANTI, ALBERTO PETTOROSSI, and MAURIZIO PROIETTI. "Solving Horn Clauses on Inductive Data Types Without Induction." Theory and Practice of Logic Programming 18, no. 3-4 (2018): 452–69. http://dx.doi.org/10.1017/s1471068418000157.

Full text

Abstract:

AbstractWe address the problem of verifying the satisfiability of Constrained Horn Clauses (CHCs) based on theories of inductively defined data structures, such as lists and trees. We propose a transformation technique whose objective is the removal of these data structures from CHCs, hence reducing their satisfiability to a satisfiability problem for CHCs on integers and booleans. We propose a transformation algorithm and identify a class of clauses where it always succeeds. We also consider an extension of that algorithm, which combines clause transformation with reasoning on integer constra

APA, Harvard, Vancouver, ISO, and other styles

4

Cathcart Burn, Toby, C. H. Luke Ong, and Steven J. Ramsay. "Higher-order constrained horn clauses for verification." Proceedings of the ACM on Programming Languages 2, POPL (2018): 1–28. http://dx.doi.org/10.1145/3158099.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

KAFLE, BISHOKSAN, JOHN P. GALLAGHER, GRAEME GANGE, PETER SCHACHTE, HARALD SØNDERGAARD, and PETER J. STUCKEY. "An iterative approach to precondition inference using constrained Horn clauses." Theory and Practice of Logic Programming 18, no. 3-4 (2018): 553–70. http://dx.doi.org/10.1017/s1471068418000091.

Full text

Abstract:

AbstractWe present a method for automatic inference of conditions on the initial states of a program that guarantee that the safety assertions in the program are not violated. Constrained Horn clauses (CHCs) are used to model the program and assertions in a uniform way, and we use standard abstract interpretations to derive an over-approximation of the set ofunsafeinitial states. The precondition then is the constraint corresponding to the complement of that set, under-approximating the set ofsafeinitial states. This idea of complementation is not new, but previous attempts to exploit it have

APA, Harvard, Vancouver, ISO, and other styles

6

Zhou, Qi, David Heath, and William Harris. "Solving Constrained Horn Clauses Using Dependence-Disjoint Expansions." Electronic Proceedings in Theoretical Computer Science 278 (September 12, 2018): 3–18. http://dx.doi.org/10.4204/eptcs.278.3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Satake, Yuki, Hiroshi Unno, and Hinata Yanagi. "Probabilistic Inference for Predicate Constraint Satisfaction." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (2020): 1644–51. http://dx.doi.org/10.1609/aaai.v34i02.5526.

Full text

Abstract:

In this paper, we present a novel constraint solving method for a class of predicate Constraint Satisfaction Problems (pCSP) where each constraint is represented by an arbitrary clause of first-order predicate logic over predicate variables. The class of pCSP properly subsumes the well-studied class of Constrained Horn Clauses (CHCs) where each constraint is restricted to a Horn clause. The class of CHCs has been widely applied to verification of linear-time safety properties of programs in different paradigms. In this paper, we show that pCSP further widens the applicability to verification o

APA, Harvard, Vancouver, ISO, and other styles

8

DE ANGELIS, EMANUELE, FABIO FIORAVANTI, ALBERTO PETTOROSSI, and MAURIZIO PROIETTI. "Predicate Pairing for program verification." Theory and Practice of Logic Programming 18, no. 2 (2017): 126–66. http://dx.doi.org/10.1017/s1471068417000497.

Full text

Abstract:

AbstractIt is well-known that the verification of partial correctness properties of imperative programs can be reduced to the satisfiability problem for constrained Horn clauses (CHCs). However, state-of-the-art solvers for constrained Horn clauses (or CHC solvers) based onpredicate abstractionare sometimes unable to verify satisfiability because they look for models that are definable in a given class 𝓐 of constraints, called 𝓐-definable models. We introduce a transformation technique, calledPredicate Pairing, which is able, in many interesting cases, to transform a set of clauses into an equ

APA, Harvard, Vancouver, ISO, and other styles

9

K, Hari Govind V., Sharon Shoham, and Arie Gurfinkel. "Solving constrained Horn clauses modulo algebraic data types and recursive functions." Proceedings of the ACM on Programming Languages 6, POPL (2022): 1–29. http://dx.doi.org/10.1145/3498722.

Full text

Abstract:

This work addresses the problem of verifying imperative programs that manipulate data structures, e.g., Rust programs. Data structures are usually modeled by Algebraic Data Types (ADTs) in verification conditions. Inductive invariants of such programs often require recursively defined functions (RDFs) to represent abstractions of data structures. From the logic perspective, this reduces to solving Constrained Horn Clauses (CHCs) modulo both ADT and RDF. The underlying logic with RDFs is undecidable. Thus, even verifying a candidate inductive invariant is undecidable. Similarly, IC3-based algor

APA, Harvard, Vancouver, ISO, and other styles

10

De Angelis, Emanuele, Fabio Fioravanti, Alberto Pettorossi, and Maurizio Proietti. "Satisfiability of constrained Horn clauses on algebraic data types: A transformation-based approach." Journal of Logic and Computation 32, no. 2 (2022): 402–42. http://dx.doi.org/10.1093/logcom/exab090.

Full text

Abstract:

Abstract We address the problem of checking the satisfiability of constrained Horn clauses (CHCs) defined on algebraic data types (ADTs), such as lists and trees. We propose a new technique for transforming CHCs defined on ADTs into CHCs where the arguments of the predicates have only basic types, such as integers and booleans. Thus, our technique avoids, during satisfiability checking, the explicit use of proof rules based on induction over the ADTs. The main extension over previous techniques for ADT removal is a new transformation rule, called differential replacement, which allows us to in

APA, Harvard, Vancouver, ISO, and other styles

More sources

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!