• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Defect Theorems with Compatibility Relations

Vesa Halava, Tero Harju, Tomi Kärki, Defect Theorems with Compatibility Relations. Semigroup Forum 76(1), 1–24, 2008.

http://dx.doi.org/10.1007/s00233-007-9013-9

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 Schutzenberger 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.

BibTeX entry:

@ARTICLE{uconv1573258,
  title = {Defect Theorems with Compatibility Relations},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi},
  journal = {Semigroup Forum},
  volume = {76},
  number = {1},
  publisher = {Springer},
  pages = {1–24},
  year = {2008},
  keywords = {unique factorization;free semigroup;stability;compatibility relation;defect theorem;partial word},
  ISSN = {0037-1912},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication