Submission date: 22 March 2018

Abstract:

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.