Crucial words and the complexity of some extremal problems for sets of prohibited words

DOI10.1016/J.JCTA.2003.12.003MaRDI QIDQ598457zbMATH OpenOpenAlexFDO

Authors Sumit K. Garg

Publication date 6 August 2004

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0205217

zbMATH Keywords

Abelian squaresCrucial wordsNP-completenessUnavoidability

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We introduced the notation of a set of prohibitions and give definitions of a complete set and a crucial word with respect to a given set of prohibitions. We consider 3 particular sets which appear in different areas of mathematics and for each of them examine the length of a crucial word. One of these sets is proved to be incomplete. The problem of determining lengths of words that are free from a set of prohibitions is shown to be NP-complete, although the related problem of whether or not a given set of prohibitions is complete is known to be effectively solvable.

Recommendations

• scientific article; zbMATH DE number 2051157
• Testing avoidability on sets of partial words is hard
• Minimal forbidden subwords
• Elementariness of a finite set of words is co-NP-complete
• UNAVOIDABLE AND ALMOST UNAVOIDABLE SETS OF WORDS

Cites work

• Abelian squares are avoidable on 4 letters
• Avoidable patterns in strings of symbols
• BLOCKING SETS OF TERMS
• Crucial words and the complexity of some extremal problems for sets of prohibited words
• scientific article; zbMATH DE number 3162927 (Why is no real title available?)
• scientific article; zbMATH DE number 3849232 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3296252 (Why is no real title available?)
• scientific article; zbMATH DE number 3375509 (Why is no real title available?)
• Maximal abelian square-free words of short length.
• On the number of Abelian square-free words on four letters
• On the synchronizing properties of certain prefix codes
• Unavoidable sets of words of uniform length

Cited in

(14)

• On uniquely k-determined permutations
• Computing abelian complexity of binary uniform morphic words
• Minimum number of holes in unavoidable sets of partial words of size three
• Elementariness of a finite set of words is co-NP-complete
• Crucial Words for Abelian Powers
• Number of holes in unavoidable sets of partial words. I.
• The Restricted Word Shadow Problem
• Unavoidable sets of partial words of uniform length
• Unavoidable sets
• Crucial words and the complexity of some extremal problems for sets of prohibited words
• On the complexity of deciding avoidability of sets of partial words
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Counting crucial permutations with respect to monotone patterns
• On shortest crucial words avoiding abelian powers

This page was built for publication: Crucial words and the complexity of some extremal problems for sets of prohibited words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598457)