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 that you have read and understand our privacy policy and code of conduct.