|
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. I ... [...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 cos ... [...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 i ... [...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 bet ... [...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 In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ..., 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 ... [...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 complete la ... [...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 ''j ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
