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

Tom Bourne, Nik Ruškuc

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)87-96
JournalTheoretical Computer Science
Volume653
Early online date5 Oct 2016
DOIs
Publication statusPublished - 15 Nov 2016

Keywords

  • Regular language
  • Star-height
  • Subword
  • Rees matrix semigroup

Fingerprint

Dive into the research topics of 'On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups'. Together they form a unique fingerprint.

Cite this