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)?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.