Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1416

Preprint Number 1416

Previous Next Preprint server

1416. Christopher D. C. Hawthorne
Remarks on formal languages and the model theory of monoids

Submission date: 22 March 2018


Given a monoid (M, ⠂ , ε) that is freely generated on a finite set Σ, it is shown that the quantifier-free definable subsets of M form a proper subclass of the star-free languages over Σ. Furthermore, a subset A ⊆ M is shown to be a regular language over Σ if and only if the φ-rank of x=x is zero, where φ(x;v) is the formula xv ∈ A. This latter result is extended to arbitrary monoids with recognizable subsets replacing regular languages.

Mathematics Subject Classification: 03C65 (Primary), 68Q45, 68Q70

Keywords and phrases:

Full text arXiv 1803.07234: pdf, ps.

Last updated: May 4 2018 11:55 Please send your corrections to: