Profinite word

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Profinite word" – news · newspapers · books · scholar · JSTOR (May 2018) (Learn how and when to remove this message)

In

.

Definition

Let A be an

whose domain is the set ${\displaystyle 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 ${\displaystyle \phi (p)\neq \phi (q)}$. For example, the morphism ${\displaystyle \phi :A^{*}\to \mathbb {Z} /2\mathbb {Z} ,w\mapsto |w|(\operatorname {mod} 2)}$ sending a word to the parity of its length separates the words ababa and abaa. Indeed ${\displaystyle \phi (ababa)=1\neq 0=\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, ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ separates ababa and abaa. More generally, ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ 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 ${\displaystyle {\frac {1}{2}}}$. The distance of p to itself is defined as 0.

This distance d is an

, that is, ${\displaystyle d(x,z)\leq \max \left\{d(x,y),d(y,z)\right\}}$. Furthermore it satisfies ${\displaystyle d(uw,vw)\leq d(u,v)}$ and ${\displaystyle d(wu,wv)\leq 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 ${\displaystyle {\frac {1}{|p|}}}$. Thus the topology defined by this metric is .

Profinite topology

The profinite completion of ${\displaystyle A^{*}}$, denoted ${\displaystyle {\widehat {A^{*}}}}$, is the

of the set of finite words under the distance defined above. The completion preserves the monoid structure.

The topology on ${\displaystyle {\widehat {A^{*}}}}$ is compact.

Any monoid morphism ${\displaystyle \phi :A^{*}\to M}$, with M finite can be extended uniquely into a monoid morphism ${\displaystyle {\widehat {\phi }}:{\widehat {A^{*}}}\to M}$, and this morphism is

(using any metric on ${\displaystyle M}$ compatible with the discrete topology). Furthermore, ${\displaystyle {\widehat {A^{*}}}}$ is the least topological space with this property.

Profinite word

A profinite word is an element of ${\displaystyle {\widehat {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 ${\displaystyle m^{\omega }}$ denote ${\displaystyle \lim _{i\to \infty }m^{i!}}$, which exists because ${\displaystyle m^{i!}}$ is a Cauchy sequence. Intuitively, to separate ${\displaystyle m^{i!}}$ and ${\displaystyle m^{i'!}}$, a monoid should count at least up to ${\displaystyle \min(i,i')}$, and hence requires at least ${\displaystyle \min(i,i')}$ elements. Since ${\displaystyle m^{i!}}$ is a Cauchy sequence, ${\displaystyle m^{\omega }}$ is indeed a profinite word.

Furthermore, the word ${\displaystyle m^{\omega }}$ is

. This is due to the fact that, for any morphism ${\displaystyle \phi :A^{*}\to N}$ with N finite, ${\displaystyle \phi (m^{i!})=\phi (m)^{i!}}$. Since N is finite, for i great enough, ${\displaystyle \phi (m)^{i!}}$ is idempotent, and the sequence is constant.

Similarly, ${\displaystyle m^{\omega +1}}$ and ${\displaystyle m^{\omega -1}}$ are defined as ${\displaystyle \lim _{n\to \infty }m^{n!+1}}$ and ${\displaystyle \lim _{n\to \infty }m^{n!-1}}$ respectively.

Profinite languages

The notion of profinite languages allows one to relate notions of

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 ${\displaystyle {\widehat {A^{*}}}\times {\widehat {A^{*}}}}$.

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

• ${\displaystyle P}$ is recognisable (as a subset of ${\displaystyle A^{*}}$),
• the closure of P, ${\displaystyle {\overline {P}}}$, is recognisable (as a subset of ${\displaystyle {\widehat {A^{*}}}}$)
• ${\displaystyle P=K\cap A^{*}}$, for some clopen K,
• ${\displaystyle {\overline {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 (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.

.