Defect theorems with compatibility relations |
| |
Authors: | Vesa Halava Tero Harju Tomi Kärki |
| |
Institution: | (1) Department of Mathematics and Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland |
| |
Abstract: | We consider words together with a compatibility relation induced by a relation on letters. Unique factorization with respect
to two arbitrary word relations R and S defines the (R,S)-freeness of the semigroup considered. We generalize the stability theorem of Schützenberger and Tilson’s closure result
for (R,S)-free semigroups. The inner and the outer (R,S)-unique factorization hull and the (R,S)-free hull of a set of words are introduced and we show how they can be computed. We prove that the (R,S)-unique factorization hulls possess a defect effect, which implies a variant of a cumulative defect theorem of word semigroups.
In addition, a defect theorem of partial words is proved as a corollary. |
| |
Keywords: | Unique factorization Free semigroup Stability Compatibility relation Defect theorem Partial word |
本文献已被 SpringerLink 等数据库收录! |
|