Free monoids and generalized metric spaces

DOI10.1016/J.EJC.2018.02.008arXiv1705.09750WikidataQ130031871 ScholiaQ130031871MaRDI QIDQ6287180FDOQ6287180

Maurice Pouzet, Ivo G. Rosenberg, Mustapha Kabil

Publication date: 26 May 2017

Abstract: Let $A$ be an ordered alphabet, $A^{ast}$ be the free monoid over $A$ ordered by the Higman ordering, and let $F(A^{ast})$ be the set of final segments of $A^{ast}$. With the operation of concatenation, this set is a monoid. We show that the submonoid $F^{circ}(A^{ast}):=F(A^{ast})setminusemptyset$ is free. The MacNeille completion $N(A^{ast})$ of $A^{ast}$ is a submonoid of $F(A^{ast})$. As a corollary, we obtain that the monoid $N^{circ}(A^{ast}):=N(A^{ast})setminusemptyset$ is free. We give an interpretation of the freeness of $F^{circ}(A^{ast})$ in the category of metric spaces over the Heyting algebra $V:=F(A^{ast})$, with the non-expansive mappings as morphisms. Each final segment of $A^{ast}$ yields the injective envelope $mathcal{S}_F$ of a two-element metric space over $V$. The uniqueness of the decomposition of $F$ is due to the uniqueness of the block decomposition of the graph $mathcal{G}_F$ associated to this injective envelope.

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Galois correspondences, closure operators (in relation to ordered sets) (06A15) Metric spaces, metrizability (54E35) Free semigroups, generators and relations, word problems (20M05) Heyting algebras (lattice-theoretic aspects) (06D20)

This page was built for publication: Free monoids and generalized metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6287180)