 | This article needs additional citations for verification .(May 2018) |
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.
Let A an alphabet. The set of profinite words over A consists of the completion of a metric space whose domain is the set 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.
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 . For example, the morphism sending a word to the parity of its length separates the words ababa and abaa. Indeed .
It is said that N separates p and q if there exists a morphism of monoids φ from M to N that separates p and q. Using the previous example, separates ababa and abaa. More generally, separates any words whose size are not congruent modulo n. In general, any two distinct words can be separated, using the monoid whose elements are the factors of p plus a fresh element 0. The morphism sends prefixes of p to themselves and everything else to 0.
The distance between two distinct words p and q is defined as the inverse of the size of the smallest monoid N separating p and q. Thus, the distance of ababa and abaa is . The distance of p to itself is defined as 0.
This distance d is an ultrametric, that is, . Furthermore it satisfies and . Since any word p can be separated from any other word using a monoid with |p|+1 elements, where |p| is the length of p, it follows that the distance between p and any other word is at least . Thus the topology defined by this metric is discrete.
The profinite completion of , denoted , is the completion of the set of finite words under the distance defined above. The completion preserves the monoid structure.
The topology on is compact.
Any monoid morphism , with M finite can be extended uniquely into a monoid morphism , and this morphism is uniformly continuous (using any metric on compatible with the discrete topology). Furthermore, is the least topological space with this property.
A profinite word is an element of . And a profinite language is a set of profinite words. Every finite word is a profinite word. A few examples of profinite words that are not finite are now given.
For m any word, let denote , which exists because is a Cauchy sequence. Intuitively, to separate and , a monoid should count at least up to , and hence requires at least elements. Since is a Cauchy sequence, is indeed a profinite word.
Furthermore, the word is idempotent. This is due to the fact that, for any morphism with N finite, . Since N is finite, for i great enough, is idempotent, and the sequence is constant.
Similarly, and are defined as and respectively.
The notion of profinite languages allows one to relate notions of semigroup theory to notions of topology. More precisely, given P a profinite language, the following statements are equivalent:
Similar statements also hold for languages P of finite words. The following conditions are equivalent.
Those characterisations are due to the more general fact that, taking the closure of a language of finite words, and restricting a profinite language to finite words are inverse operations, when they are applied to recognisable languages.
In mathematics, a profinite group is a topological group that is in a certain sense assembled from a system of finite groups.
In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.
In mathematics, in particular abstract algebra, a graded ring is a ring such that the underlying additive group is a direct sum of abelian groups such that . The index set is usually the set of nonnegative integers or the set of integers, but can be any monoid. The direct sum decomposition is usually referred to as gradation or grading.
In analytic number theory and related branches of mathematics, a complex-valued arithmetic function is a Dirichlet character of modulus if for all integers and :
In mathematics, the adele ring of a global field is a central object of class field theory, a branch of algebraic number theory. It is the restricted product of all the completions of the global field and is an example of a self-dual topological ring.
In mathematics, group cohomology is a set of mathematical tools used to study groups using cohomology theory, a technique from algebraic topology. Analogous to group representations, group cohomology looks at the group actions of a group G in an associated G-moduleM to elucidate the properties of the group. By treating the G-module as a kind of topological space with elements of representing n-simplices, topological properties of the space may be computed, such as the set of cohomology groups . The cohomology groups in turn provide insight into the structure of the group G and G-module M themselves. Group cohomology plays a role in the investigation of fixed points of a group action in a module or space and the quotient module or space with respect to a group action. Group cohomology is used in the fields of abstract algebra, homological algebra, algebraic topology and algebraic number theory, as well as in applications to group theory proper. As in algebraic topology, there is a dual theory called group homology. The techniques of group cohomology can also be extended to the case that instead of a G-module, G acts on a nonabelian G-group; in effect, a generalization of a module to non-Abelian coefficients.
In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in the 1930s in the course of his investigation of Boolean algebras, which culminated in his representation theorem for Boolean algebras.
In mathematics, a congruence subgroup of a matrix group with integer entries is a subgroup defined by congruence conditions on the entries. A very simple example is the subgroup of invertible 2 × 2 integer matrices of determinant 1 in which the off-diagonal entries are even. More generally, the notion of congruence subgroup can be defined for arithmetic subgroups of algebraic groups; that is, those for which we have a notion of 'integral structure' and can define reduction maps modulo an integer.
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.
In mathematics, the Grothendieck group, or group of differences, of a commutative monoid M is a certain abelian group. This abelian group is constructed from M in the most universal way, in the sense that any abelian group containing a homomorphic image of M will also contain a homomorphic image of the Grothendieck group of M. The Grothendieck group construction takes its name from a specific case in category theory, introduced by Alexander Grothendieck in his proof of the Grothendieck–Riemann–Roch theorem, which resulted in the development of K-theory. This specific case is the monoid of isomorphism classes of objects of an abelian category, with the direct sum as its operation.
In mathematics, a quasi-finite field is a generalisation of a finite field. Standard local class field theory usually deals with complete valued fields whose residue field is finite, but the theory applies equally well when the residue field is only assumed quasi-finite.
In algebraic geometry, a morphism of schemes generalizes a morphism of algebraic varieties just as a scheme generalizes an algebraic variety. It is, by definition, a morphism in the category of schemes.
In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place. Traces were introduced by Pierre Cartier and Dominique Foata in 1969 to give a combinatorial proof of MacMahon's master theorem. Traces are used in theories of concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while non-commuting letters stand for locks, synchronization points or thread joins.
In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words that represent the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms. The most widely studied shift spaces are the subshifts of finite type and the sofic shifts.
In mathematics, an approximately finite-dimensional (AF) C*-algebra is a C*-algebra that is the inductive limit of a sequence of finite-dimensional C*-algebras. Approximate finite-dimensionality was first defined and described combinatorially by Ola Bratteli. Later, George A. Elliott gave a complete classification of AF algebras using the K0 functor whose range consists of ordered abelian groups with sufficiently nice order structure.
In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some homomorphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.
In computer science, more precisely in automata theory, a rational set of a monoid is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under union, product and Kleene star. Rational sets are useful in automata theory, formal languages and algebra.
In abstract algebra, a branch of mathematics, an affine monoid is a commutative monoid that is finitely generated, and is isomorphic to a submonoid of a free abelian group . Affine monoids are closely connected to convex polyhedra, and their associated algebras are of much use in the algebraic study of these geometric objects.
In mathematics, a profinite integer is an element of the ring
In mathematics, and more precisely in semigroup theory, a variety of finite semigroups is a class of semigroups having some nice algebraic properties. Those classes can be defined in two distinct ways, using either algebraic notions or topological notions. Varieties of finite monoids, varieties of finite ordered semigroups and varieties of finite ordered monoids are defined similarly.
Pin, Jean-Éric (2016-11-30). Mathematical Foundations of Automata Theory (PDF). pp. 130–139.
Almeida, Jorge (1994). Finite semigroups and universal algebra. River Edge, NJ: World Scientific Publishing Co. Inc. ISBN 981-02-1895-8.
