pith. sign in

arxiv: 1603.06236 · v2 · pith:AHTEPHYRnew · submitted 2016-03-20 · 💻 cs.FL · math.GR

On the star-height of factor counting languages and their relationship to Rees zero-matrix semigroups

classification 💻 cs.FL math.GR
keywords languagesstar-heightcontiguousfactorgeneralisednumberoccursrees
0
0 comments X
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.