|
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 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 coinduc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Corecursion
In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is '' generative recursion'' which may lack a definite "direction" inherent in corecursion and recursion. Where recursion allows programs to operate on arbitrarily complex data, so long as they can be reduced to simple data (base cases), corecursion allows programs to produce arbitrarily complex and potentially infinite data structures, such as streams, so long as it can be produced from simple data (base cases) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
F-coalgebra
In mathematics, specifically in category theory, an F-coalgebra is a structure defined according to a functor F, with specific properties as defined below. For both algebras and coalgebras, a functor is a convenient and general way of organizing a signature. This has applications in computer science: examples of coalgebras include lazy, infinite data structures, such as streams, and also transition systems. F-coalgebras are dual to F-algebras. Just as the class of all algebras for a given signature and equational theory form a variety, so does the class of all F-coalgebras satisfying a given equational theory form a covariety, where the signature is given by F. Definition Let :F : \mathcal\longrightarrow \mathcal be an endofunctor on a category \mathcal. An F-coalgebra is an object A of \mathcal together with a morphism :\alpha : A \longrightarrow FA of \mathcal, usually written as (A, \alpha). An F-coalgebra homomorphism from (A, \alpha) to another F-coalgebra (B, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bisimilarity
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 state transition system, labelled state transition system (S, \Lambda, →), where S 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 R and its converse relation, converse R^T are simulation preorder, simulations. From this follows that the symmetric closure of a bisimulation is a bisimulation, and that each symmetric simulation is a bisimulation. Thus some aut ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Corecursion
In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is '' generative recursion'' which may lack a definite "direction" inherent in corecursion and recursion. Where recursion allows programs to operate on arbitrarily complex data, so long as they can be reduced to simple data (base cases), corecursion allows programs to produce arbitrarily complex and potentially infinite data structures, such as streams, so long as it can be produced from simple data (base cases) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Non-well-founded Set Theory
Non-well-founded set theories are variants of axiomatic set theory that allow sets to be elements of themselves and otherwise violate the rule of well-foundedness. In non-well-founded set theories, the foundation axiom of ZFC is replaced by axioms implying its negation. The study of non-well-founded sets was initiated by Dmitry Mirimanoff in a series of papers between 1917 and 1920, in which he formulated the distinction between well-founded and non-well-founded sets; he did not regard well-foundedness as an axiom. Although a number of axiomatic systems of non-well-founded sets were proposed afterwards, they did not find much in the way of applications until Peter Aczel’s hyperset theory in 1988. The theory of non-well-founded sets has been applied in the logical modelling of non-terminating computational processes in computer science (process algebra and final semantics), linguistics and natural language semantics ( situation theory), philosophy (work on the Liar Paradox ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Structural Induction
Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction. Structural induction is used to prove that some proposition ''P''(''x'') holds for all ''x'' of some sort of recursively defined structure, such as formulas, lists, or trees. A well-founded partial order is defined on the structures ("subformula" for formulas, "sublist" for lists, and "subtree" for trees). The structural induction proof is a proof that the proposition holds for all the minimal structures and that if it holds for the immediate substructures of a certain structure ''S'', then it must hold ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Functor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and maps between these algebraic objects are associated to continuous maps between spaces. Nowadays, functors are used throughout modern mathematics to relate various categories. Thus, functors are important in all areas within mathematics to which category theory is applied. The words ''category'' and ''functor'' were borrowed by mathematicians from the philosophers Aristotle and Rudolf Carnap, respectively. The latter used ''functor'' in a linguistic context; see function word. Definition Let ''C'' and ''D'' be categories. A functor ''F'' from ''C'' to ''D'' is a mapping that * associates each object X in ''C'' to an object F(X) in ''D'', * associates each morphism f \colon X \to Y in ''C'' to a morphism F(f) \colon F(X) \to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Category Of Sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition of morphisms is the composition of functions. Many other categories (such as the category of groups, with group homomorphisms as arrows) add structure to the objects of the category of sets and/or restrict the arrows to functions of a particular kind. Properties of the category of sets The axioms of a category are satisfied by Set because composition of functions is associative, and because every set ''X'' has an identity function id''X'' : ''X'' → ''X'' which serves as identity element for function composition. The epimorphisms in Set are the surjective maps, the monomorphisms are the injective maps, and the isomorphisms are the bijective maps. The empty set serves as the initial object in Set with empty functions as morph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fixed Point (mathematics)
A fixed point (sometimes shortened to fixpoint, also known as an invariant point) is a value that does not change under a given transformation. Specifically, in mathematics, a fixed point of a function is an element that is mapped to itself by the function. In physics, the term fixed point can refer to a temperature that can be used as a reproducible reference point, usually defined by a phase change or triple point. Fixed point of a function Formally, is a fixed point of a function if belongs to both the domain and the codomain of , and . For example, if is defined on the real numbers by f(x) = x^2 - 3 x + 4, then 2 is a fixed point of , because . Not all functions have fixed points: for example, , has no fixed points, since is never equal to for any real number. In graphical terms, a fixed point means the point is on the line , or in other words the graph of has a point in common with that line. Fixed-point iteration In numerical analysis, ''fixed-poin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stream (computing)
In computer science, a stream is a sequence of data elements made available over time. A stream can be thought of as items on a conveyor belt being processed one at a time rather than in large batches. Streams are processed differently from batch data – normal functions cannot operate on streams as a whole, as they have potentially unlimited data, and formally, streams are ''codata'' (potentially unlimited), not data (which is finite). Functions that operate on a stream, producing another stream, are known as filters, and can be connected in pipelines, analogously to function composition. Filters may operate on one item of a stream at a time, or may base an item of output on multiple items of input, such as a moving average. Examples The term "stream" is used in a number of similar ways: * "Stream editing", as with sed, awk, and perl. Stream editing processes a file or files, in-place, without having to load the file(s) into a user interface. One example of such use is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Repeating Decimal
A repeating decimal or recurring decimal is decimal representation of a number whose digits are periodic (repeating its values at regular intervals) and the infinitely repeated portion is not zero. It can be shown that a number is rational if and only if its decimal representation is repeating or terminating (i.e. all except finitely many digits are zero). For example, the decimal representation of becomes periodic just after the decimal point, repeating the single digit "3" forever, i.e. 0.333.... A more complicated example is , whose decimal becomes periodic at the ''second'' digit following the decimal point and then repeats the sequence "144" forever, i.e. 5.8144144144.... At present, there is no single universally accepted notation or phrasing for repeating decimals. The infinitely repeated digit sequence is called the repetend or reptend. If the repetend is a zero, this decimal representation is called a terminating decimal rather than a repeating decimal, since the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.gif "Click for more on -> Repeating Decimal")