Constructing partial words with subword complexities not achievable by full words
From MaRDI portal
Publication:428848
DOI10.1016/j.tcs.2012.01.039zbMath1244.68063MaRDI QIDQ428848
Jarett Schwartz, Aleksandar Chakarov, Lucas Manuelli, Slater Stich, Francine 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
polynomial complexity; subword complexity; combinatorics on words; automata and formal languages; partial words; intermediate complexity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity and special factors
- Partial words and a theorem of Fine and Wilf
- Complexity of sequences and dynamical systems
- Sequences with subword complexity \(2n\)
- On the complexity of infinite sequences
- Rauzy's conjecture on billiards in the cube
- Toeplitz words, generalized periodicity and periodically iterated morphisms
- Complexity of Toeplitz sequences
- Billiard complexity in rational polyhedra
- Complexity of trajectories in rectangular billiards
- The subword complexity of a class of infinite binary words
- Hard Counting Problems for Partial Words
- Binary De Bruijn Partial Words with One Hole
- Représentation géométrique de suites de complexité $2n+1$
- Complexity of sequences defined by billiard in the cube
- Automatic Sequences
- Algorithmic Combinatorics on Partial Words
