A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Zebra factorizations in free semigroups
Tekijät: Ehrenfeucht A, Harju T, Rozenberg G
Kustantaja: SPRINGER-VERLAG
Julkaisuvuosi: 2004
Lehti:: Semigroup Forum
Tietokannassa oleva lehden nimi: SEMIGROUP FORUM
Lehden akronyymi: SEMIGROUP FORUM
Vuosikerta: 68
Numero: 3
Aloitussivu: 365
Lopetussivu: 372
Sivujen määrä: 8
ISSN: 0037-1912
DOI: https://doi.org/10.1007/s00233-003-0030-z
Tiivistelmä
Let S be a semigroup of words over an alphabet A. Let Omega(S) consist of those elements w of S for which every prefix and suffix of w belongs to S. We show that Omega(S) is a free semigroup. Moreover, S is called separative if also the complement S-c = A(+)\ S is a semigroup. There are uncountably many separative semigroups over A, if A has at least two letters. We prove that if S is separative, then every word w is an element of A(+) has a unique minimum factorization w = z(1)z(2) ... z(n) with respect to Omega(S) and Omega(S-c), where z(i) is an element of Omega(S) boolean OROmega(S-c) and n is as small as possible.
Let S be a semigroup of words over an alphabet A. Let Omega(S) consist of those elements w of S for which every prefix and suffix of w belongs to S. We show that Omega(S) is a free semigroup. Moreover, S is called separative if also the complement S-c = A(+)\ S is a semigroup. There are uncountably many separative semigroups over A, if A has at least two letters. We prove that if S is separative, then every word w is an element of A(+) has a unique minimum factorization w = z(1)z(2) ... z(n) with respect to Omega(S) and Omega(S-c), where z(i) is an element of Omega(S) boolean OROmega(S-c) and n is as small as possible.
Turun yliopiston Tutkimustietojärjestelmän portaali