Profinite word

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (June 2024) (Learn how and when to remove this template message)

|

(Learn how and when to remove this template message)

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.

## Contents

* 1 Definition
* 1.1 Separation
* 1.2 Distance
* 1.3 Profinite topology
* 1.4 Profinite word
* 2 Profinite languages
* 3 References

## Definition

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* 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 ϕ(p)≠ϕ(q). For example, the morphism ϕ:A*->ℤ/2ℤ,w↦|w|(mod⁡2) sending a word to the parity of its length separates the words ababa and abaa. Indeed ϕ(ababa)=1≠0=ϕ(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, ℤ/2ℤ separates ababa and abaa. More generally, ℤ/nℤ 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.

### Distance

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. The distance of p to itself is defined as 0.

This distance d is an ultrametric, that is, d(x,z)≤max⁡{d(x,y),d(y,z)}. Furthermore it satisfies d(uw,vw)≤d(u,v) and d(wu,wv)≤d(u,v). 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 1|p|. Thus the topology defined by this metric is discrete.

### Profinite topology

The profinite completion of A*, denoted A*^, is the completion of the set of finite words under the distance defined above. The completion preserves the monoid structure.

The topology on A*^ is compact.

Any monoid morphism ϕ:A*->M, with M finite can be extended uniquely into a monoid morphism ϕ^:A*^->M, and this morphism is uniformly continuous (using any metric on M compatible with the discrete topology). Furthermore, A*^ is the least topological space with this property.

### Profinite word

A profinite word is an element of A*^. 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 mω denote limi->∞mi!, which exists because mi! is a Cauchy sequence. Intuitively, to separate mi! and mi′!, a monoid should count at least up to min⁡(i,i′), and hence requires at least min⁡(i,i′) elements. Since mi! is a Cauchy sequence, mω is indeed a profinite word.

Furthermore, the word mω is idempotent. This is due to the fact that, for any morphism ϕ:A*->N with N finite, ϕ(mi!)=ϕ(m)i!. Since N is finite, for i great enough, ϕ(m)i! is idempotent, and the sequence is constant.

Similarly, mω+1 and mω−1 are defined as limn->∞mn!+1 and limn->∞mn!−1 respectively.

## Profinite languages

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:

* P is clopen.
* P is recognizable,
* The syntactic congruence of P is clopen, as a subset of A*^×A*^.

Similar statements also hold for languages P of finite words. The following conditions are equivalent.

* P is recognisable (as a subset of A*),
* the closure of P, P‾, is recognisable (as a subset of A*^)
* P=K∩A*, for some clopen K,
* P‾ is clopen.

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.

## References

Pin, Jean-Éric (2022-02-18). Mathematical Foundations of Automata Theory. pp. 130–139. https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf.

Almeida, Jorge (1994). Finite semigroups and universal algebra. River Edge, NJ: World Scientific Publishing Co. Inc.. ISBN 981-02-1895-8.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Profinite word. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Profinite_word&oldid=4149868"