Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations.
I am already familiar with a few well known ones:
- Sets describable in the first order logic of $(\mathbb{N},+)$
- The character counts (image under the Parikh map) of regular languages
- The character counts of context free languages
- Finite unions of disjoint fundamental linear sets (per R. Ito's "Every Semilinear Set is a Finite Union of Disjoint Linear Sets")
- I conjecture that the semilinear sets are exactly the "piecewise periodic" sets for some nice notion of pieces (https://mathoverflow.net/questions/442142/are-semilinear-sets-piecewise-periodic)
Are there any other known characterizations? Does anything interesting happen if, perhaps, we consider the set of "words on $\mathbb{N}^d$" (functions $f: \mathbb{N}^d \to \Sigma$ where $\Sigma$ is some finite alphabet, with the preimage of a singleton being semilinear)?
