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 be an alphabet. The set of profinite words over A consists of the completion of a metric space whose domain is the set
A*
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)
\phi:A*\toZ/2Z,w\mapsto|w|(\operatorname{mod}2)
\phi(ababa)=1\ne0=\phi(abaa)
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,
Z/2Z
Z/nZ
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
12 | |
This distance d is an ultrametric, that is,
d(x,z)\leqmax\left\{d(x,y),d(y,z)\right\}
d(uw,vw)\led(u,v)
d(wu,wv)\led(u,v)
1 | |
|p| |
The profinite completion of
A*
\widehat{A*}
The topology on
\widehat{A*}
Any monoid morphism
\phi:A*\toM
\widehat\phi:\widehat{A*}\toM
M
\widehat{A*}
A profinite word is an element of
\widehat{A*}
For m any word, let
m\omega
\limi\toinftymi!
mi!
mi!
mi'!
min(i,i')
min(i,i')
mi!
m\omega
Furthermore, the word
m\omega
\phi:A*\toN
\phi(mi!)=\phi(m)i!
\phi(m)i!
Similarly,
m\omega+1
m\omega-1
\limn\toinftymn!+
\limn\toinftymn!-1
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:
\widehat{A*} x \widehat{A*}
Similar statements also hold for languages P of finite words. The following conditions are equivalent.
P
A*
\overlineP
\widehat{A*}
P=K\capA*
\overlineP
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.
Book: Pin. Jean-Éric. Jean-Éric Pin. Mathematical Foundations of Automata Theory. 2016-11-30. 130–139.
Book: Almeida. Jorge. Finite semigroups and universal algebra. 1994. World Scientific Publishing Co. Inc.. River Edge, NJ. 981-02-1895-8.