Constructing partial words with subword complexities not achievable by full words

DOI10.1016/J.TCS.2012.01.039MaRDI QIDQ428848zbMATH OpenOpenAlexFDO

Authors Aleksandar Chakarov, Lucas Manuelli, Jarett Schwartz, Slater Stich, F. Blanchet-Sadri

Publication date 25 June 2012

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

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

zbMATH Keywords

combinatorics on wordspolynomial complexityautomata and formal languagespartial wordsintermediate complexitysubword complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Recommendations

• On minimal Sturmian partial words
• Recurrent Partial Words and Representable Sets.
• Recurrent partial words
• Binary de Bruijn partial words with one hole
• On minimal Sturmian partial words

Cites work

• scientific article; zbMATH DE number 1948496 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 5051582 (Why is no real title available?)
• Algorithmic Combinatorics on Partial Words
• Automatic Sequences
• Billiard complexity in rational polyhedra
• Binary de Bruijn partial words with one hole
• Complexity and special factors
• Complexity of Toeplitz sequences
• Complexity of sequences and dynamical systems
• Complexity of sequences defined by billiard in the cube
• Complexity of trajectories in rectangular billiards
• Hard counting problems for partial words
• On the complexity of infinite sequences
• Partial words and a theorem of Fine and Wilf
• Rauzy's conjecture on billiards in the cube
• Représentation géométrique de suites de complexité $2n+1$
• Sequences with subword complexity \(2n\)
• The subword complexity of a class of infinite binary words
• Toeplitz words, generalized periodicity and periodically iterated morphisms

Cited in

(6)

• Binary de Bruijn partial words with one hole
• Algorithmic combinatorics on partial words
• A note on constructing infinite binary words with polynomial subword complexity
• Recurrent partial words
• On minimal Sturmian partial words
• On minimal Sturmian partial words

This page was built for publication: Constructing partial words with subword complexities not achievable by full words

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