|
Stutter Bisimulation
In theoretical computer science, a stutter bisimulation is a relationship between two transition systems, abstract machines that model computation. It is defined coinductively and generalizes the idea of bisimulations. A bisimulation matches up the states of a machine such that transitions correspond; a stutter bisimulation allows transitions to be matched to finite path fragments. Definition In '' Principles of Model Checking'', Baier and Katoen define a stutter bisimulation for a single transition system and later adapt it to a relation on two transition systems. A stutter bisimulation for \text=(S, \text, \to, I, \text, L) is a binary relation ''R'' on ''S'' such that for all (''s''1,''s''2) in ''R'': # s_1, s_2 have the same labels # If s_1\to s_1' is a valid transition and (s_1',s_2)\not\in R then there exists a finite path fragment s_2u_1\cdots u_n s_2' (n\ge 0) such that each pair (s_1, u_i) is in ''R'' and (s_1',s_2') is in ''R'' # If s_2\to s_2' is a valid transition and ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Theoretical Computer Science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Association for Computing Machinery, ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with A Mathematical Theory of Communication, a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of Hebbian learning, learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of neural networks and para ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
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] [Amazon] |
Coinduction
In computer science, coinduction is a technique for defining and proving properties of systems of concurrent interacting objects. Coinduction is the mathematical dual to structural induction. Coinductively defined data types are known as codata and are typically infinite data structures, such as streams. As a definition or specification, coinduction describes how an object may be "observed", "broken down" or "destructed" into simpler objects. As a proof technique, it may be used to show that an equation is satisfied by all possible implementations of such a specification. To generate and manipulate codata, one typically uses corecursive functions, in conjunction with lazy evaluation. Informally, rather than defining a function by pattern-matching on each of the inductive constructors, one defines each of the "destructors" or "observers" over the function result. In programming, co-logic programming (co-LP for brevity) "is a natural generalization of logic programming and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Bisimulation
In theoretical computer science a bisimulation is a binary relation between state transition systems, associating systems that behave in the same way in that one system simulates the other and vice versa. Intuitively two systems are bisimilar if they, assuming we view them as playing a ''game'' according to some rules, match each other's moves. In this sense, each of the systems cannot be distinguished from the other by an observer. Formal definition Given a labeled state transition system , where is a set of states, \Lambda is a set of labels and → is a set of labelled transitions (i.e., a subset of S \times \Lambda \times S), a bisimulation is a binary relation R \subseteq S \times S, such that both and its converse R^T are simulations. From this follows that the symmetric closure of a bisimulation is a bisimulation, and that each symmetric simulation is a bisimulation. Thus some authors define bisimulation as a symmetric simulation. Equivalently, is a bisimulatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Principles Of Model Checking
''Principles of Model Checking'' is a textbook on model checking, an area of computer science that automates the problem of determining if a machine meets specification requirements. It was written by Christel Baier and Joost-Pieter Katoen, and published in 2008 by MIT Press. Synopsis The introduction and first chapter outline the field of model checking: a model of a machine or process can be analysed to see if desirable properties hold. For instance, a vending machine might satisfy the property "the balance can never fall below €0,00". A video game might enforce the rule "if the player has 0 lives then the game ends in a loss". Both the vending machine and video game can be modelled as transition systems. Model checking is the process of describing such requirements in mathematical language, and automating proofs that the model satisfies the requirements, or discovery of counterexamples if the model is faulty. The second chapter focuses on creating an appropriate model for ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Christel Baier
Christel Baier (born 26 September 1965) is a German theoretical computer scientist known for her work in model checking, temporal logic, and automata theory. She is a professor at TU Dresden, where she holds the chair for Algebraic and Logic Foundations of Computer Science in the Faculty of Computer Science. Baier is the editor-in-chief of ''Acta Informatica''. Education and career Baier earned a diploma in mathematics at the University of Mannheim in 1990, and stayed at the same university for graduate study in computer science, completing her Ph.D. there in 1994. Her dissertation, ''Transitionssystem- und Baum-Semantiken für CCS'', was supervised by Mila Majster-Cederbaum. She earned a habilitation at Mannheim in 1999. She became an associate professor for computer science at the University of Bonn in 1999, and moved to TU Dresden as a professor in 2006. Book With Joost-Pieter Katoen, Baier is coauthor of the book ''Principles of Model Checking'' (MIT Press, 2008). Recognit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
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] [Amazon] |
Binary Relation
In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs (x, y), where x is an element of X and y is an element of Y. It encodes the common concept of relation: an element x is ''related'' to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation. An example of a binary relation is the "divides" relation over the set of prime numbers \mathbb and the set of integers \mathbb, in which each prime p is related to each integer z that is a Divisibility, multiple of p, but not to an integer that is not a Multiple (mathematics), multiple of p. In this relation, for instance, the prime number 2 is related to numbers such as -4, 0, 6, 10, but not to 1 or 9, just as the prime number 3 is related to 0, 6, and 9, but not to 4 or 13. Binary relations ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
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] [Amazon] |
