Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952452 | Theoretical Computer Science | 2016 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tom Bourne, Nik Ruškuc,