|
Kripke Structure
A Kripke structure is a variation of the transition system, originally proposed by Saul Kripke, used in model checking to represent the behavior of a system. It consists of a graph whose nodes represent the reachable states of the system and whose edges represent state transitions, together with a labelling function which maps each node to a set of properties that hold in the corresponding state. Temporal logics are traditionally interpreted in terms of Kripke structures. Formal definition Let be a set of ''atomic propositions'', i.e. boolean-valued expressions formed from variables, constants and predicate symbols. Clarke et al. define a Kripke structure over as a 4-tuple consisting of * a finite set of states . * a set of initial states . * a transition relation such that is left-total, i.e., such that . * a labeling (or ''interpretation'') function . Since is left-total, it is always possible to construct an infinite path through the Kripke structure. A deadlock sta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Transition System
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a singleton, the system is essentially unlabeled, and a simpler definition that omits the labels is possible. Transition systems coincide mathematically with abstract rewriting systems (as explained further in this article) and directed graphs. They differ from finite-state automata in several ways: * The set of states is not necessarily finite, or even countable. * The set of transitions is not necessarily finite, or even countable. * No "start" state or "final" states are given. Transition systems can be represented as directed graphs. Formal definition Formally, a transition system is a pair (S, T) where S is a set of states ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
ω-language
In formal language theory within theoretical computer science, an infinite word is an infinite-length sequence (specifically, an ω-length sequence) of symbols, and an ω-language is a set of infinite words. Here, ω refers to the first infinite ordinal number, modeling a set of natural numbers. Formal definition Let Σ be a set of symbols (not necessarily finite). Following the standard definition from formal language theory, Σ* is the set of all ''finite'' words over Σ. Every finite word has a length, which is a natural number. Given a word ''w'' of length ''n'', ''w'' can be viewed as a function from the set → Σ, with the value at ''i'' giving the symbol at position ''i''. The infinite words, or ω-words, can likewise be viewed as functions from \mathbb to Σ. The set of all infinite words over Σ is denoted Σω. The set of all finite ''and'' infinite words over Σ is sometimes written Σ∞ or Σ≤ω. Thus an ω-language ''L'' over Σ is a subset of Σω. Operations ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Temporal Logic
In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal logic, modal temporal logic with modalities referring to time. In LTL, one can encode formula (logic), formulae about the future of path (graph theory), paths, e.g., a condition will eventually be true, a condition will be true until another fact becomes true, etc. It is a fragment of the more complex CTL*, which additionally allows branching time and quantifier (logic), quantifiers. LTL is sometimes called propositional temporal logic (PTL). In terms of expressive power (computer science), expressive power, LTL is a fragment of first-order logic. LTL was first proposed for the formal verification of computer programs by Amir Pnueli in 1977. Syntax LTL is built up from a finite set of propositional variables ''AP'', the logical connective, logical operators ¬ and ∨, and the Temporal logic, temporal modal operators X (some literature uses O or N) and U. Formally, the set of LTL formulas over ''AP'' is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kripke Semantics
Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke and André Joyal. It was first conceived for modal logics, and later adapted to intuitionistic logic and other non-classical systems. The development of Kripke semantics was a breakthrough in the theory of non-classical logics, because the model theory of such logics was almost non-existent before Kripke (algebraic semantics existed, but were considered 'syntax in disguise'). Semantics of modal logic The language of propositional modal logic consists of a countably infinite set of propositional variables, a set of truth-functional connectives (in this article \to and \neg), and the modal operator \Box ("necessarily"). The modal operator \Diamond ("possibly") is (classically) the dual of \Box and may be defined in terms of necessity like so: \ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Model Checking
In computer science, model checking or property checking is a method for checking whether a finite-state model of a system meets a given specification (also known as correctness). This is typically associated with hardware or software systems, where the specification contains liveness requirements (such as avoidance of livelock) as well as safety requirements (such as avoidance of states representing a system crash). In order to solve such a problem algorithmically, both the model of the system and its specification are formulated in some precise mathematical language. To this end, the problem is formulated as a task in logic, namely to check whether a structure satisfies a given logical formula. This general concept applies to many kinds of logic and many kinds of structures. A simple model-checking problem consists of verifying whether a formula in the propositional logic is satisfied by a given structure. Overview Property checking is used for verification when two ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modal μ-calculus
In theoretical computer science, the modal μ-calculus (Lμ, Lμ, sometimes just μ-calculus, although this can have a more general meaning) is an extension of propositional modal logic (with many modalities) by adding the least fixed point operator μ and the greatest fixed point operator ν, thus a fixed-point logic. The (propositional, modal) μ-calculus originates with Dana Scott and Jaco de Bakker, and was further developed by Dexter Kozen into the version most used nowadays. It is used to describe properties of labelled transition systems and for verifying these properties. Many temporal logics can be encoded in the μ-calculus, including CTL* and its widely used fragments—linear temporal logic and computational tree logic. An algebraic view is to see it as an algebra of monotonic functions over a complete lattice, with operators consisting of functional composition plus the least and greatest fixed point operators; from this viewpoint, the modal μ-calculus is o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Joost-Pieter Katoen
Joost-Pieter Katoen (born October 6, 1964) is a Dutch theoretical computer scientist based in Germany. He is distinguished professor in Computer Science and head of the Software Modeling and Verification Group at RWTH Aachen University. Furthermore, he is part-time associated to the Formal Methods & Tools group at the University of Twente. Education Katoen received his master's degree with distinction in Computer Science from the University of Twente in 1987. In 1990, he was awarded a Professional Doctorate in Engineering from the Eindhoven University of Technology, and in 1996, he received his Ph.D. in computer science from the University of Twente. Research Katoen's research focuses on developing mathematical verification methods for assessing the accuracy of programs and computer systems. Katoen's main research interests are formal methods, computer aided verification, in particular model checking and deductive program verification, concurrency theory, and semantics. His de ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Moore Machine
In the theory of computation, a Moore machine is a finite-state machine whose current output values are determined only by its current state. This is in contrast to a Mealy machine, whose output values are determined both by its current state and by the values of its inputs. Like other finite state machines, in Moore machines, the input typically influences the next state. Thus the input may indirectly influence subsequent outputs, but not the current or immediate output. The Moore machine is named after Edward F. Moore, who presented the concept in a 1956 paper, “ Gedanken-experiments on Sequential Machines.” Formal definition A Moore machine can be defined as a 6-tuple (S, s_0, \Sigma, O, \delta, G) consisting of the following: * A finite set of states S * A start state (also called initial state) s_0 which is an element of S * A finite set called the input alphabet \Sigma * A finite set called the output alphabet O * A transition function \delta : S \times \Sigma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deadlock (computer Science)
In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock. Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, because in these contexts systems often use software or hardware locks to arbitrate shared resources and implement process synchronization. In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process. If a process remains indefinitely unable to change its state because resources requested by it are being used by another process that itself is waiting, then the system is said to be in a deadlock. In a communications system, deadlocks occur mainly due to loss ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Saul Kripke
Saul Aaron Kripke (; November 13, 1940 – September 15, 2022) was an American analytic philosophy, analytic philosopher and logician. He was Distinguished Professor of Philosophy at the Graduate Center of the City University of New York and emeritus professor at Princeton University. From the 1960s until his death, he was a central figure in a number of fields related to mathematical logic, mathematical and modal logic, philosophy of language and philosophy of mathematics, mathematics, metaphysics, epistemology, and recursion theory. Kripke made influential and original contributions to logic, especially modal logic. His principal contribution is a semantics for modal logic involving possible worlds, now called Kripke semantics. He received the 2001 Schock Prize in Logic and Philosophy. Kripke was also partly responsible for the revival of metaphysics and Scientific essentialism, essentialism after the decline of logical positivism, claiming Metaphysical necessity, necessity is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Left-total
In mathematics, a binary relation ''R'' ⊆ ''X''×''Y'' between two sets ''X'' and ''Y'' is total (or left total) if the source set ''X'' equals the domain . Conversely, ''R'' is called right total if ''Y'' equals the range . When ''f'': ''X'' → ''Y'' is a function, the domain of ''f'' is all of ''X'', hence ''f'' is a total relation. On the other hand, if ''f'' is a partial function, then the domain may be a proper subset of ''X'', in which case ''f'' is not a total relation. "A binary relation is said to be total with respect to a universe of discourse just in case everything in that universe of discourse stands in that relation to something else." from |
