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

Tom Bourne; Nik Ruškuc

doi:10.1016/j.tcs.2016.09.024

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 journal › Article › peer-review

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 language	English
Pages (from-to)	87-96
Journal	Theoretical Computer Science
Volume	653
Early online date	5 Oct 2016
DOIs	https://doi.org/10.1016/j.tcs.2016.09.024
Publication status	Published - 15 Nov 2016

Keywords

Regular language
Star-height
Subword
Rees matrix semigroup

Access to Document

10.1016/j.tcs.2016.09.024

Bourne_2016_Semigroups_TheoreticalCompSci_AAM
© 2016, Elsevier. This work is made available online in accordance with the publisher’s policies. This is the author created, accepted version manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at www.sciencedirect.com / https://dx.doi.org/10.1016/j.tcs.2016.09.024
Accepted author manuscript, 296 KB

Handle.net

Persistent link

Automata Languages Decidability: Automata, Languages, Decidability in Algebra
Ruskuc, N. (PI) & Quick, M. (CoI)
EPSRC
1/03/10 → 31/05/14
Project: Standard
EPSRC GR/S53503/01: Applications of Automata and Languages in the Theory of Pattern Classes of Permutations
Ruskuc, N. (PI), Linton, S. (CoI) & Robertson, E. (CoI)
EPSRC
1/02/04 → 31/01/07
Project: Standard

Counting subwords and other results related to the generalised star-height problem for regular languages
Bourne, T. (Author), Ruskuc, N. (Supervisor) & Roney-Dougal, C. (Supervisor), 7 Dec 2017
Student thesis: Doctoral Thesis (PhD)

Cite this

@article{e8ec086c5cdc4ab783e317c64cfdb491,

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

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 = "Regular language, Star-height, Subword, Rees matrix semigroup",

author = "Tom Bourne and Nik Ru{\v s}kuc",

year = "2016",

month = nov,

day = "15",

doi = "10.1016/j.tcs.2016.09.024",

language = "English",

volume = "653",

pages = "87--96",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Bourne, Tom

AU - Ruškuc, Nik

PY - 2016/11/15

Y1 - 2016/11/15

N2 - 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.

AB - 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.

KW - Regular language

KW - Star-height

KW - Subword

KW - Rees matrix semigroup

U2 - 10.1016/j.tcs.2016.09.024

DO - 10.1016/j.tcs.2016.09.024

M3 - Article

SN - 0304-3975

VL - 653

SP - 87

EP - 96

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

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

Abstract

Keywords

Access to Document

Handle.net

Fingerprint

Projects

Automata Languages Decidability: Automata, Languages, Decidability in Algebra

EPSRC GR/S53503/01: Applications of Automata and Languages in the Theory of Pattern Classes of Permutations

Student theses

Counting subwords and other results related to the generalised star-height problem for regular languages

Cite this