|
Profinite Word
In mathematics, more precisely in formal language theory, the profinite words are a generalization of the notion of finite words into a complete topological space. This notion allows the use of topology to study languages and finite semigroups. For example, profinite words are used to give an alternative characterization of the algebraic notion of a variety of finite semigroups. Definition Let ''A'' an alphabet. The set of profinite words over ''A'' consists of the completion of a metric space whose domain is the set A^* of words over ''A''. The distance used to define the metric is given using a notion of separation of words. Those notions are now defined. Separation Let ''M'' and ''N'' be monoids, and let ''p'' and ''q'' be elements of the monoid ''M''. Let ''φ'' be a morphism of monoids from ''M'' to ''N''. It is said that the morphism ''φ'' separates ''p'' and ''q'' if \phi(p)\ne\phi(q). For example, the morphism \phi:A^*\to \mathbb Z/2\mathbb Z, w\mapsto , w, (\operat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting poin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Topology
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest topology that can be given on a set. Every subset is open in the discrete topology so that in particular, every singleton subset is an open set in the discrete topology. Definitions Given a set X: A metric space (E,d) is said to be '' uniformly discrete'' if there exists a ' r > 0 such that, for any x,y \in E, one has either x = y or d(x,y) > r. The topology underlying a metric space can be discrete, without the metric being uniformly discrete: for example the usual metric on the set \left\. Properties The underlying uniformity on a discrete metric space is the discrete uniformity, and the underlying topology on a discrete uniform space is the discrete topology. Thus, the different notions of discrete space are compatible with ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the theoretical areas precisely. The Association for Computing Machinery, ACM's ACM SIGACT, 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 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 n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Formal Languages
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symbols, letters, or tokens that concatenate into strings of the language. Each string concatenated from symbols of this alphabet is called a word, and the words that belong to a particular formal language are sometimes called ''well-formed words'' or ''well-formed formulas''. A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules. In computer science, formal languages are used among others as the basis for defining the grammar of programming languages and formalized versions of subsets of natural languages in which the words of the language represent concepts that are associated with particular meanings or semantics. In computational complexit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Closure (topology)
In topology, the closure of a subset of points in a topological space consists of all points in together with all limit points of . The closure of may equivalently be defined as the union of and its boundary, and also as the intersection of all closed sets containing . Intuitively, the closure can be thought of as all the points that are either in or "near" . A point which is in the closure of is a point of closure of . The notion of closure is in many ways dual to the notion of interior. Definitions Point of closure For S as a subset of a Euclidean space, x is a point of closure of S if every open ball centered at x contains a point of S (this point can be x itself). This definition generalizes to any subset S of a metric space X. Fully expressed, for X as a metric space with metric d, x is a point of closure of S if for every r > 0 there exists some s \in S such that the distance d(x, s) < r ( is allowed). Another way to express this i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Syntactic Congruence
In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L. Syntactic quotient The free monoid on a given set is the monoid whose elements are all the strings of zero or more elements from that set, with string concatenation as the monoid operation and the empty string as the identity element. Given a subset S of a free monoid M, one may define sets that consist of formal left or right inverses of elements in S. These are called quotients, and one may define right or left quotients, depending on which side one is concatenating. Thus, the right quotient of S by an element m from M is the set :S \ / \ m=\. Similarly, the left quotient is :m \setminus S=\. Syntactic equivalence The syntactic quotient induces an equivalence relation on M, called the syntactic relation, or syntactic equivalence (induced by S). The ''right syntactic equivalence'' is the equivalence relation :s \sim_S t \ \Leftrigh ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Recognizable Set
In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra. This notion is different from the notion of recognizable language. Indeed, the term "recognizable" has a different meaning in computability theory. Definition Let N be a monoid, a subset S\subseteq N is recognized by a monoid M if there exists a morphism \phi from N to M such that S=\phi^(\phi(S)), and recognizable if it is recognized by some finite monoid. This means that there exists a subset T of M (not necessarily a submonoid of M) such that the image of S is in T and the image of N \setminus S is in M \setminus T. Example Let A be an alphabet: the set A^* of words over A is a monoid, the free monoid on A. The recognizable subsets of A^* are precisely the regular languages. Indeed, such a language is recognized by the transition monoid ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clopen
In topology, a clopen set (a portmanteau of closed-open set) in a topological space is a set which is both open and closed. That this is possible may seem counter-intuitive, as the common meanings of and are antonyms, but their mathematical definitions are not mutually exclusive. A set is closed if its complement is open, which leaves the possibility of an open set whose complement is also open, making both sets both open closed, and therefore clopen. As described by topologist James Munkres, unlike a door, "a set can be open, or closed, or both, or neither!" emphasizing that the meaning of "open"/"closed" for is unrelated to their meaning for (and so the open/closed door dichotomy does not transfer to open/closed sets). This contrast to doors gave the class of topological spaces known as "door spaces" their name. Examples In any topological space X, the empty set and the whole space X are both clopen. Now consider the space X which consists of the union of the two o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semigroup Theory
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', denotes the result of applying the semigroup operation to the ordered pair . Associativity is formally expressed as that for all ''x'', ''y'' and ''z'' in the semigroup. Semigroups may be considered a special case of magmas, where the operation is associative, or as a generalization of groups, without requiring the existence of an identity element or inverses. The closure axiom is implied by the definition of a binary operation on a set. Some authors thus omit it and specify three axioms for a group and only one axiom (associativity) for a semigroup. As in the case of groups or magmas, the semigroup operation need not be commutative, so ''x''·''y'' is not necessarily equal to ''y''·''x''; a well-known example of an operation that is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Idempotent
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of places in abstract algebra (in particular, in the theory of projectors and closure operators) and functional programming (in which it is connected to the property of referential transparency). The term was introduced by American mathematician Benjamin Peirce in 1870 in the context of elements of algebras that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from + '' potence'' (same + power). Definition An element x of a set S equipped with a binary operator \cdot is said to be ''idempotent'' under \cdot if : . The ''binary operation'' \cdot is said to be ''idempotent'' if : . Examples * In the monoid (\mathbb, \times) of the natural numbers with multiplication, on ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cauchy Sequence
In mathematics, a Cauchy sequence (; ), named after Augustin-Louis Cauchy, is a sequence whose elements become arbitrarily close to each other as the sequence progresses. More precisely, given any small positive distance, all but a finite number of elements of the sequence are less than that given distance from each other. It is not sufficient for each term to become arbitrarily close to the term. For instance, in the sequence of square roots of natural numbers: a_n=\sqrt n, the consecutive terms become arbitrarily close to each other: a_-a_n = \sqrt-\sqrt = \frac d. (Actually, any m > \left(\sqrt + d\right)^2 suffices.) As a result, despite how far one goes, the remaining terms of the sequence never get close to ; hence the sequence is not Cauchy. The utility of Cauchy sequences lies in the fact that in a complete metric space (one where all such sequences are known to converge to a limit), the criterion for convergence depends only on the terms of the sequence itself, as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Uniformly Continuous
In mathematics, a real function f of real numbers is said to be uniformly continuous if there is a positive real number \delta such that function values over any function domain interval of the size \delta are as close to each other as we want. In other words, for a uniformly continuous real function of real numbers, if we want function value differences to be less than any positive real number \epsilon, then there is a positive real number \delta such that , f(x) - f(y), 0 there exists a real number \delta > 0 such that for every x,y \in X with d_1(x,y) 0 such that for every x,y \in X , , x - y, 0 \; \forall x \in X \; \forall y \in X : \, d_1(x,y) 0 , \forall x \in X , and \forall y \in X ) are used. * Alternatively, f is said to be uniformly continuous if there is a function of all positive real numbers \varepsilon, \delta(\varepsilon) representing the maximum positive real number, such that for every x,y \in X if d_1(x,y) 0 such that for every y \in X w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Idempotent")
