Zebra Factorizations in Free Semigroups |
| |
Authors: | Andrzej Ehrenfeucht Tero Harju Grzegorz Rozenberg |
| |
Affiliation: | (1) Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309-0347, USA;(2) Department of Mathematics, University of Turku, FIN-20014 Turku, Finland;(3) Leiden Institute for Advanced Computer Science, Leiden University, Niels Bohrweg 1 2333 CA Leiden, The Netherlands and Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309-0347, USA |
| |
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^+setminus 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 in A^+$ has a unique minimum factorization $w = z_1z_2 cdots z_n$ with respect to $Omega(S)$ and $Omega(S^c)$, where $z_i in Omega(S) cup Omega(S^c)$ and $n$ is as small as possible. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|