Green languages and growth of free inverse monoids
Abstract
Motivated by recent work on conjugacy languages in groups, we introduce a general framework for studying \emph{languages of representatives} associated to equivalence relations on finitely generated semigroups. After developing this notion in full generality, we particularize it to Green's relations and obtain the corresponding Green languages, which form the central objects of this article. For free inverse monoids, we describe these languages via Munn trees and establish several structural relations among them, including characterizations of the π-, β-, β-, and β-languages. We then investigate the formal language-theoretic complexity of these Green languages. For free inverse monoids of rank at least two, we show that β-Geo is context-free and co-context-free but not regular, while β-Geo, β-Geo, and π-Geo are neither context-free nor co-context-free. In contrast, in the monogenic case, π-Geo is regular and the remaining Green languages are deterministic context-free. We further relate these results to the ShortLex language and the growth of free inverse monoids, proving in particular that (FIMX,X) is growth tight. The article concludes with a collection of open problems and directions for future research.
Related
- Convexity of inverse spectral Green kernels and nondegeneracy of Robin centers in convex domains
- Fast Nanophotonic Inverse Design using Precomputed Numerical Green Functions
- Weighted potential and Green systems with Dini coefficients and primitive growth
- Uniqueness in inverse elastic scattering from traction-free polygonal obstacles with a single incoming wave
- An inverse free boundary problem
BibTeX
@misc{bodart2026green,
title = {{Green languages and growth of free inverse monoids}},
author = {Corentin Bodart and AndrΓ© Carvalho and Ana-Catarina C. Monteiro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.35251},
eprint = {2609.35251},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35251},
}
RIS
TY - UNPB
TI - Green languages and growth of free inverse monoids
AU - Corentin Bodart
AU - AndrΓ© Carvalho
AU - Ana-Catarina C. Monteiro
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2609.35251
UR - https://arxiv.org/abs/2609.35251
AB - Motivated by recent work on conjugacy languages in groups, we introduce a general framework for studying \emph{languages of representatives} associated to equivalence relations on finitely generated semigroups. After developing this notion in full generality, we particularize it to Green's relations and obtain the corresponding Green languages, which form the central objects of this article. For free inverse monoids, we describe these languages via Munn trees and establish several structural relations among them, including characterizations of the π-, β-, β-, and β-languages. We then investigate the formal language-theoretic complexity of these Green languages. For free inverse monoids of rank at least two, we show that β-Geo is context-free and co-context-free but not regular, while β-Geo, β-Geo, and π-Geo are neither context-free nor co-context-free. In contrast, in the monogenic case, π-Geo is regular and the remaining Green languages are deterministic context-free. We further relate these results to the ShortLex language and the growth of free inverse monoids, proving in particular that (FIM_X,X) is growth tight. The article concludes with a collection of open problems and directions for future research.
ER -