|
Bekić's Theorem
In computability theory, Bekić's theorem or Bekić's lemma is a theorem about fixed-points which allows splitting a mutual recursion into recursions on one variable at a time. It was created by Austrian Hans Bekić (1936-1982) in 1969, and published posthumously in a book by Cliff Jones in 1984. The theorem is set up as follows. Consider two operators f : P \times Q \to P and g : P \times Q \to Q on pointed directed-complete partial orders P and Q, continuous in each component. Then define the operator (f, g)(x, y) = (f (x, y), g(x, y)). This is monotone with respect to the product order (componentwise order). By the Kleene fixed-point theorem, it has a least fixed point \mu (x, y).(f, g)(x, y), a pair (x_0, y_0) in P \times Q such that f (x_0, y_0) = x_0 and g(x_0, y_0) = y_0. Bekić's theorem (called the "bisection lemma" in his notes) is that the simultaneous least fixed point \mu (x, y).(f, g)(x, y) = (x_0,y_0) can be separated into a series of least fixed points on P and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computability Theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: * What does it mean for a function on the natural numbers to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fixed-point Theorem
In mathematics, a fixed-point theorem is a result saying that a function ''F'' will have at least one fixed point (a point ''x'' for which ''F''(''x'') = ''x''), under some conditions on ''F'' that can be stated in general terms. Some authors claim that results of this kind are amongst the most generally useful in mathematics. In mathematical analysis The Banach fixed-point theorem (1922) gives a general criterion guaranteeing that, if it is satisfied, the procedure of iterating a function yields a fixed point. By contrast, the Brouwer fixed-point theorem (1911) is a non- constructive result: it says that any continuous function from the closed unit ball in ''n''-dimensional Euclidean space to itself must have a fixed point, but it doesn't describe how to find the fixed point (See also Sperner's lemma). For example, the cosine function is continuous in ˆ’1,1and maps it into ˆ’1, 1 and thus must have a fixed point. This is clear when examining a sketched graph of the c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cliff Jones (computer Scientist)
Clifford "Cliff" B. Jones (born 1 June 1944) is a British computer scientist, specializing in research into formal methods. He undertook a late DPhil at the Oxford University Computing Laboratory (now the Oxford University Department of Computer Science) under Tony Hoare, awarded in 1981. Jones' thesis proposed an extension to Hoare logic for handling concurrent programs, rely/guarantee. Prior to his DPhil, Jones worked for IBM, between the Hursley and Vienna Laboratories. In Vienna, Jones worked with Peter Lucas, Dines Bjørner and others on the Vienna Development Method (VDM), originally as a method for specifying the formal semantics of programming languages, and subsequently for specifying and verifying programs. Cliff Jones was a professor at the Victoria University of Manchester in the 1980s and early 1990s, worked in industry at Harlequin for a period, and is now a Professor of Computing Science at Newcastle University. He has been editor-in-chief of the ''Formal Aspe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Partial Order
In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science: in denotational semantics and domain theory. Definitions A complete partial order, abbreviated cpo, can refer to any of the following concepts depending on context. * A partially ordered set is a directed-complete partial order (dcpo) if each of its directed subsets has a supremum. A subset of a partial order is directed if it is non-empty and every pair of elements has an upper bound in the subset. In the literature, dcpos sometimes also appear under the label up-complete poset. * A partially ordered set is a pointed directed-complete partial order if it is a dcpo with a least element. They are sometimes abbreviated cppos. * A partially ordered set is a ω-complete partial order (ω-cpo) if it ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scott Continuity
In mathematics, given two partially ordered sets ''P'' and ''Q'', a function ''f'': ''P'' → ''Q'' between them is Scott-continuous (named after the mathematician Dana Scott) if it preserves all directed suprema. That is, for every directed subset ''D'' of ''P'' with supremum in ''P'', its image has a supremum in ''Q'', and that supremum is the image of the supremum of ''D'', i.e. \sqcup f = f(\sqcup D), where \sqcup is the directed join. When Q is the poset of truth values, i.e. Sierpiński space, then Scott-continuous functions are characteristic functions of open sets, and thus Sierpiński space is the classifying space for open sets. A subset ''O'' of a partially ordered set ''P'' is called Scott-open if it is an upper set and if it is inaccessible by directed joins, i.e. if all directed sets ''D'' with supremum in ''O'' have non-empty intersection with ''O''. The Scott-open subsets of a partially ordered set ''P'' form a topology on ''P'', the Scott topology. A function b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Product Order
In mathematics, given two preordered sets A and B, the product order (also called the coordinatewise orderDavey & Priestley, ''Introduction to Lattices and Order'' (Second Edition), 2002, p. 18 or componentwise order) is a partial ordering on the Cartesian product A \times B. Given two pairs \left(a_1, b_1\right) and \left(a_2, b_2\right) in A \times B, declare that \left(a_1, b_1\right) \leq \left(a_2, b_2\right) if and only if a_1 \leq a_2 and b_1 \leq b_2. Another possible ordering on A \times B is the lexicographical order, which is a total ordering. However the product order of two totally ordered sets is not in general total; for example, the pairs (0, 1) and (1, 0) are incomparable in the product order of the ordering 0 < 1 with itself. The lexicographic order of totally ordered sets is a of their product order, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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: :Kleene Fixed-Point Theorem. Suppose (L, \sqsubseteq) is a directed-complete partial order (dcpo) with a least element, and let f: L \to L be a Scott-continuous (and therefore monotone) function. Then f has a least fixed point, which is the supremum of the ascending Kleene chain of f. The ascending Kleene chain of ''f'' is the chain :\bot \sqsubseteq f(\bot) \sqsubseteq f(f(\bot)) \sqsubseteq \cdots \sqsubseteq f^n(\bot) \sqsubseteq \cdots obtained by iterating ''f'' on the least element ⊥ of ''L''. Expressed in a formula, the theorem states that :\textrm(f) = \sup \left(\left\\right) where \textrm denotes the least fixed point. Although Tarski's fixed point theorem does not consider how fixed points can be computed by iterating ''f'' from some seed (also, it pertains to monotone functions on complet ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Lattice
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' Specifically, every non-empty finite lattice is complete. Complete lattices appear in many applications in mathematics and computer science. Being a special instance of lattices, they are studied both in order theory and universal algebra. Complete lattices must not be confused with complete partial orders (''cpo''s), which constitute a strictly more general class of partially ordered sets. More specific complete lattices are complete Boolean algebras and complete Heyting algebras (''locales''). Formal definition A partially ordered set (''L'', ≤) is a ''complete lattice'' if every subset ''A'' of ''L'' has both a greatest lower bound (the infimum, also called the ''meet'') and a least upper bound (the supremum, also called the ' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Knaster–Tarski Theorem
In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following: :''Let'' (''L'', ≤) ''be a complete lattice and let f : L → L be an monotonic function (w.r.t. ≤ ). Then the set of fixed points of f in L also forms a complete lattice under ≤ .'' It was Tarski who stated the result in its most general form, and so the theorem is often known as Tarski's fixed-point theorem. Some time earlier, Knaster and Tarski established the result for the special case where ''L'' is the lattice of subsets of a set, the power set lattice. The theorem has important applications in formal semantics of programming languages and abstract interpretation. A kind of converse of this theorem was proved by Anne C. Davis: If every order preserving function ''f'' : ''L'' → ''L'' on a lattice ''L'' has a fixed point, then ''L'' is a complete lattice. Consequences: least and greatest fixe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Monotonic Function
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory. In calculus and analysis In calculus, a function f defined on a subset of the real numbers with real values is called ''monotonic'' if and only if it is either entirely non-increasing, or entirely non-decreasing. That is, as per Fig. 1, a function that increases monotonically does not exclusively have to increase, it simply must not decrease. A function is called ''monotonically increasing'' (also ''increasing'' or ''non-decreasing'') if for all x and y such that x \leq y one has f\!\left(x\right) \leq f\!\left(y\right), so f preserves the order (see Figure 1). Likewise, a function is called ''monotonically decreasing'' (also ''decreasing'' or ''non-increasing'') if, whenever x \leq y, then f\!\left(x\right) \geq f\!\left(y\r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
F-algebra
In mathematics, specifically in category theory, ''F''-algebras generalize the notion of algebraic structure. Rewriting the algebraic laws in terms of morphisms eliminates all references to quantified elements from the axioms, and these algebraic laws may then be glued together in terms of a single functor ''F'', the ''signature''. ''F''-algebras can also be used to represent data structures used in programming, such as lists and trees. The main related concepts are initial ''F''-algebras which may serve to encapsulate the induction principle, and the dual construction ''F''-coalgebras. Definition If C is a category, and F : C \rightarrow C is an endofunctor of C, then an F-algebra is a tuple (A, \alpha), where A is an object of C and \alpha is a C- morphism F(A) \rightarrow A. The object A is called the ''carrier'' of the algebra. When it is permissible from context, algebras are often referred to by their carrier only instead of the tuple. A homomorphism from an F-al ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Automated Theorem Prover
Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a major impetus for the development of computer science. Logical foundations While the roots of formalised logic go back to Aristotle, the end of the 19th and early 20th centuries saw the development of modern logic and formalised mathematics. Frege's ''Begriffsschrift'' (1879) introduced both a complete propositional calculus and what is essentially modern predicate logic. His ''Foundations of Arithmetic'', published 1884, expressed (parts of) mathematics in formal logic. This approach was continued by Russell and Whitehead in their influential '' Principia Mathematica'', first published 1910–1913, and with a revised second edition in 1927. Russell and Whitehead thought they could derive all mathematical truth using axioms and infere ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
