Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 

Predicate transformer semantics

Index Predicate transformer semantics

Predicate transformer semantics were introduced by Edsger Dijkstra in his seminal paper "Guarded commands, nondeterminacy and formal derivation of programs". [1]

54 relations: Abstract interpretation, Abstract syntax, ACM Transactions on Programming Languages and Systems, Algorithm, Assertion (software development), Automated reasoning, Axiomatic semantics, B-Method, Concurrent computing, Continuation-passing style, Coq, Cryptography, Deductive reasoning, Denotational semantics, Distributed computing, Dynamic logic (modal logic), Edsger W. Dijkstra, ESC/Java, Evaluation strategy, First-order logic, Formal Aspects of Computing, Formal system, Frama-C, Free variables and bound variables, Gödel's completeness theorem, Guarded Command Language, Haskell (programming language), Hoare logic, Imperative programming, Kleene fixed-point theorem, Leslie Lamport, Loop invariant, Loop variant, Monad (functional programming), Monotonic function, Natural number, Niklaus Wirth, Operational semantics, Partial function, Postcondition, Precondition, Predicate (mathematical logic), Proof assistant, Ralph-Johan Back, Randomized algorithm, Refinement calculus, Satisfiability modulo theories, Semantics (computer science), Separation logic, Set theory, ..., Symbolic execution, Tuple, Type theory, Well-founded relation. Expand index (4 more) »

Abstract interpretation

In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices.

New!!: Predicate transformer semantics and Abstract interpretation · See more »

Abstract syntax

In computer science, the abstract syntax of data is its structure described as a data type (possibly, but not necessarily, an abstract data type), independent of any particular representation or encoding.

New!!: Predicate transformer semantics and Abstract syntax · See more »

ACM Transactions on Programming Languages and Systems

The ACM Transactions on Programming Languages and Systems (TOPLAS) is a bimonthly peer-reviewed scientific journal on programming languages published by the Association for Computing Machinery since 1979.

New!!: Predicate transformer semantics and ACM Transactions on Programming Languages and Systems · See more »

Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: Predicate transformer semantics and Algorithm · See more »

Assertion (software development)

In computer programming, an assertion is a statement that a predicate (Boolean-valued function, i.e. a true–false expression) is always true at that point in code execution.

New!!: Predicate transformer semantics and Assertion (software development) · See more »

Automated reasoning

Automated reasoning is an area of computer science and mathematical logic dedicated to understanding different aspects of reasoning.

New!!: Predicate transformer semantics and Automated reasoning · See more »

Axiomatic semantics

Axiomatic semantics is an approach based on mathematical logic for proving the correctness of computer programs.

New!!: Predicate transformer semantics and Axiomatic semantics · See more »

B-Method

The B method is a method of software development based on B, a tool-supported formal method based on an abstract machine notation, used in the development of computer software.

New!!: Predicate transformer semantics and B-Method · See more »

Concurrent computing

Concurrent computing is a form of computing in which several computations are executed during overlapping time periods—concurrently—instead of sequentially (one completing before the next starts).

New!!: Predicate transformer semantics and Concurrent computing · See more »

Continuation-passing style

In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation.

New!!: Predicate transformer semantics and Continuation-passing style · See more »

Coq

In computer science, Coq is an interactive theorem prover.

New!!: Predicate transformer semantics and Coq · See more »

Cryptography

Cryptography or cryptology (from κρυπτός|translit.

New!!: Predicate transformer semantics and Cryptography · See more »

Deductive reasoning

Deductive reasoning, also deductive logic, logical deduction is the process of reasoning from one or more statements (premises) to reach a logically certain conclusion.

New!!: Predicate transformer semantics and Deductive reasoning · See more »

Denotational semantics

In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called denotations) that describe the meanings of expressions from the languages.

New!!: Predicate transformer semantics and Denotational semantics · See more »

Distributed computing

Distributed computing is a field of computer science that studies distributed systems.

New!!: Predicate transformer semantics and Distributed computing · See more »

Dynamic logic (modal logic)

Dynamic logic is an extension of modal logic originally intended for reasoning about computer programs and later applied to more general complex behaviors arising in linguistics, philosophy, AI, and other fields.

New!!: Predicate transformer semantics and Dynamic logic (modal logic) · See more »

Edsger W. Dijkstra

Edsger Wybe Dijkstra (11 May 1930 – 6 August 2002) was a Dutch systems scientist, programmer, software engineer, science essayist, and early pioneer in computing science.

New!!: Predicate transformer semantics and Edsger W. Dijkstra · See more »

ESC/Java

ESC/Java (and more recently ESC/Java2), the "Extended Static Checker for Java," is a programming tool that attempts to find common run-time errors in Java programs at compile time.

New!!: Predicate transformer semantics and ESC/Java · See more »

Evaluation strategy

Evaluation strategies are used by programming languages to determine when to evaluate the argument(s) of a function call (for function, also read: operation, method, or relation) and what kind of value to pass to the function.

New!!: Predicate transformer semantics and Evaluation strategy · See more »

First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

New!!: Predicate transformer semantics and First-order logic · See more »

Formal Aspects of Computing

Formal Aspects of Computing (FAOC) is a peer-reviewed scientific journal published by Springer Science+Business Media, covering the area of formal methods and associated topics in computer science.

New!!: Predicate transformer semantics and Formal Aspects of Computing · See more »

Formal system

A formal system is the name of a logic system usually defined in the mathematical way.

New!!: Predicate transformer semantics and Formal system · See more »

Frama-C

Frama-C stands for Framework for Modular Analysis of C programs.

New!!: Predicate transformer semantics and Frama-C · See more »

Free variables and bound variables

In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place.

New!!: Predicate transformer semantics and Free variables and bound variables · See more »

Gödel's completeness theorem

Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic.

New!!: Predicate transformer semantics and Gödel's completeness theorem · See more »

Guarded Command Language

The Guarded Command Language (GCL) is a language defined by Edsger Dijkstra for predicate transformer semantics.

New!!: Predicate transformer semantics and Guarded Command Language · See more »

Haskell (programming language)

Haskell is a standardized, general-purpose compiled purely functional programming language, with non-strict semantics and strong static typing.

New!!: Predicate transformer semantics and Haskell (programming language) · See more »

Hoare logic

Hoare logic (also known as Floyd–Hoare logic or Hoare rules) is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs.

New!!: Predicate transformer semantics and Hoare logic · See more »

Imperative programming

In computer science, imperative programming is a programming paradigm that uses statements that change a program's state.

New!!: Predicate transformer semantics and Imperative programming · See more »

Kleene fixed-point theorem

In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following: The ascending Kleene chain of f is the chain obtained by iterating f on the least element ⊥ of L. Expressed in a formula, the theorem states that where \textrm denotes the least fixed point.

New!!: Predicate transformer semantics and Kleene fixed-point theorem · See more »

Leslie Lamport

Leslie B. Lamport (born February 7, 1941) is an American computer scientist.

New!!: Predicate transformer semantics and Leslie Lamport · See more »

Loop invariant

In computer science, a loop invariant is a property of a program loop that is true before (and after) each iteration.

New!!: Predicate transformer semantics and Loop invariant · See more »

Loop variant

In computer science, a loop variant is a mathematical function defined on the state space of a computer program whose value is monotonically decreased with respect to a (strict) well-founded relation by the iteration of a while loop under some invariant conditions, thereby ensuring its termination.

New!!: Predicate transformer semantics and Loop variant · See more »

Monad (functional programming)

In functional programming, a monad is a design pattern that defines how functions, actions, inputs, and outputs can be used together to build generic types, with the following organization.

New!!: Predicate transformer semantics and Monad (functional programming) · See more »

Monotonic function

In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order.

New!!: Predicate transformer semantics and Monotonic function · See more »

Natural number

In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country").

New!!: Predicate transformer semantics and Natural number · See more »

Niklaus Wirth

Niklaus Emil Wirth (born 15 February 1934) is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering.

New!!: Predicate transformer semantics and Niklaus Wirth · See more »

Operational semantics

Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execution and procedures, rather than by attaching mathematical meanings to its terms (denotational semantics).

New!!: Predicate transformer semantics and Operational semantics · See more »

Partial function

In mathematics, a partial function from X to Y (written as or) is a function, for some subset X ′ of X.

New!!: Predicate transformer semantics and Partial function · See more »

Postcondition

In computer programming, a postcondition is a condition or predicate that must always be true just after the execution of some section of code or after an operation in a formal specification.

New!!: Predicate transformer semantics and Postcondition · See more »

Precondition

In computer programming, a precondition is a condition or predicate that must always be true just prior to the execution of some section of code or before an operation in a formal specification.

New!!: Predicate transformer semantics and Precondition · See more »

Predicate (mathematical logic)

In mathematical logic, a predicate is commonly understood to be a Boolean-valued function P: X→, called the predicate on X. However, predicates have many different uses and interpretations in mathematics and logic, and their precise definition, meaning and use will vary from theory to theory.

New!!: Predicate transformer semantics and Predicate (mathematical logic) · See more »

Proof assistant

In computer science and mathematical logic, a proof assistant or interactive theorem prover is a software tool to assist with the development of formal proofs by human-machine collaboration.

New!!: Predicate transformer semantics and Proof assistant · See more »

Ralph-Johan Back

Ralph-Johan Back is a Finnish computer scientist.

New!!: Predicate transformer semantics and Ralph-Johan Back · See more »

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

New!!: Predicate transformer semantics and Randomized algorithm · See more »

Refinement calculus

The refinement calculus is a formalized approach to stepwise refinement for program construction.

New!!: Predicate transformer semantics and Refinement calculus · See more »

Satisfiability modulo theories

In computer science and mathematical logic, the satisfiability modulo theories (SMT) problem is a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality.

New!!: Predicate transformer semantics and Satisfiability modulo theories · See more »

Semantics (computer science)

In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages.

New!!: Predicate transformer semantics and Semantics (computer science) · See more »

Separation logic

In computer science, separation logic is an extension of Hoare logic, a way of reasoning about programs.

New!!: Predicate transformer semantics and Separation logic · See more »

Set theory

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects.

New!!: Predicate transformer semantics and Set theory · See more »

Symbolic execution

In computer science, symbolic execution (also symbolic evaluation) is a means of analyzing a program to determine what inputs cause each part of a program to execute.

New!!: Predicate transformer semantics and Symbolic execution · See more »

Tuple

In mathematics, a tuple is a finite ordered list (sequence) of elements.

New!!: Predicate transformer semantics and Tuple · See more »

Type theory

In mathematics, logic, and computer science, a type theory is any of a class of formal systems, some of which can serve as alternatives to set theory as a foundation for all mathematics.

New!!: Predicate transformer semantics and Type theory · See more »

Well-founded relation

In mathematics, a binary relation, R, is called well-founded (or wellfounded) on a class X if every non-empty subset S ⊆ X has a minimal element with respect to R, that is an element m not related by sRm (for instance, "s is not smaller than m") for any s ∈ S. In other words, a relation is well founded if Some authors include an extra condition that R is set-like, i.e., that the elements less than any given element form a set.

New!!: Predicate transformer semantics and Well-founded relation · See more »

Redirects here:

Weakest liberal precondition, Weakest precondition, Weakest precondition calculus.

References

[1] https://en.wikipedia.org/wiki/Predicate_transformer_semantics

OutgoingIncoming
Hey! We are on Facebook now! »