首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号