A1 Refereed original research article in a scientific journal
Zebra factorizations in free semigroups
Authors: Ehrenfeucht A, Harju T, Rozenberg G
Publisher: SPRINGER-VERLAG
Publication year: 2004
Journal:: Semigroup Forum
Journal name in source: SEMIGROUP FORUM
Journal acronym: SEMIGROUP FORUM
Volume: 68
Issue: 3
First page : 365
Last page: 372
Number of pages: 8
ISSN: 0037-1912
DOI: https://doi.org/10.1007/s00233-003-0030-z
Abstract
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.
UTU Research Portal