Defect theorems with compatibility relations.
The well known `defect theorem' of words states that if a set of \(n\) words in the free semigroup \(A^+\) generated by the letters of an alphabet \(A\) satisfies a nontrivial relation, then these words can be expressed simultaneously as products of at most \(n-1\) words. Putting restrictions on the \(n-1\) words give variants of the defect theorem. Another formulation of the defect theorem is the following: Let \(X\subseteq A^+\) be a finite set of words and let \(B\) be the base of the `free hull' of \(X\), that is, the smallest free semigroup containing \(X\). Then \(|B|\leq|X|\) (where \(|B|,|X|\) denote the cardinalities of \(B,X\) respectively), and \(|B|=|X|\) if and only if \(X\) is a code. In this paper, the authors study defect theorems with `word relations' \(R\subseteq A^+\times A^+\). More specifically, they generalize the above mentioned concepts with respect to these relations \(R\), which are reflexive and symmetric relations induced by their restrictions on the letters of \(A\). These word relations were introduced by the authors in order to generalize the notion of `partial word'.
- A periodicity result of partial words with one hole
- Codes, orderings, and partial words
- Conjugacy on partial words.
- DNA Computing
- Elementary homomorphisms and a solution of the DOL sequence equivalence problem
- scientific article; zbMATH DE number 3943051 (Why is no real title available?)
- scientific article; zbMATH DE number 1834684 (Why is no real title available?)
- Local periods and binary partial words: an algorithm
- Many aspects of defect theorems
- Partial words and a theorem of Fine and Wilf
- Partial words and a theorem of Fine and Wilf revisited
- Partial words and the critical factorization theorem
- Partial words and the interaction property of periods
- Periodicity on partial words
- Presentations et presentations simplifiables d'un monoide simplifiable
- Primitive partial words
- Relational codes of words
- Sur le théorème du defaut
- The decidability of the dol prefix problem
- The intersection of free submonoids of a free monoid is free
- On the defect theorem and simplifiability
- On the relation between cardinalities of 1-orbits and 1-information of words
- Many aspects of defect theorems
- Relational codes of words
- On the defect theorem for trees
- Defect theorem in the plane
- Compatibility relations on codes and free monoids
- The theorem of Fine and Wilf for relational periods
- scientific article; zbMATH DE number 1761920 (Why is no real title available?)
This page was built for publication: Defect theorems with compatibility relations.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2480767)
