On the star-height of factor counting languages and their relationship to Rees zero-matrix semigroups
classification
💻 cs.FL
math.GR
keywords
languagesstar-heightcontiguousfactorgeneralisednumberoccursrees
read the original abstract
Given a word $w$ over a finite alphabet, we consider, in three special cases, the generalised star-height of the languages in which $w$ occurs as a contiguous subword (factor) an exact number of times and of the languages in which $w$ occurs as a contiguous subword modulo a fixed number, and prove that in each case it is at most one. We use these combinatorial results to show that any language recognised by a Rees (zero-)matrix semigroup over an abelian group is of generalised star-height at most one.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.