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

Defect Theorems with Compatibility Relation

Vesa Halava, Tero Harju, Tomi Kärki, Defect Theorems with Compatibility Relation. TUCS Technical Reports 778, Turku Centre for Computer Science, 2006.

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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaKa06b,
  title = {Defect Theorems with Compatibility Relation},
  author = {Halava, Vesa and Harju, Tero and Kärki, Tomi},
  number = {778},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {unique factorization, free semigroup, stability, compatibility relation, defect theorem, partial word},
  ISBN = {952-12-1763-4},
}

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

Edit publication