Codes, orderings, and partial words

DOI10.1016/j.tcs.2004.08.011zbMath1086.68108OpenAlexW1989728373MaRDI QIDQ706621

Francine Blanchet-Sadri

Publication date: 9 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.08.011

zbMATH Keywords

Partial orderingAntichainWordCodeDominoPartial word

Mathematics Subject Classification ID

Combinatorics on words (68R15) Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Prefix, length-variable, comma-free codes (94A45)

Related Items

Testing primitivity on partial words ⋮ Compatibility relations on codes and free monoids ⋮ Equations on partial words ⋮ Relational codes of words ⋮ Freeness of partial words ⋮ Relations on words ⋮ Defect theorems with compatibility relations. ⋮ Primitive partial words ⋮ Partial words and the critical factorization theorem ⋮ Regular languages of partial words ⋮ A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE ⋮ Overlap-freeness in infinite partial words ⋮ The theorem of Fine and Wilf for relational periods

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A periodicity result of partial words with one hole
• Partial words and a theorem of Fine and Wilf
• Decipherability of codes
• Periodicity on partial words
• Anti-commutative languages and n-codes
• Conjugacy on partial words.
• Local periods and binary partial words: an algorithm
• On unique, multiset, and set decipherability of three-word codes
• Deciding multiset decipherability
• On free monoids partially ordered by embedding
• Ordering by Divisibility in Abstract Algebras
• Partial words and a theorem of Fine and Wilf revisited