Nondeterministic automatic complexity of overlap-free and almost square-free words

zbMath1334.68173arXiv1402.3856MaRDI QIDQ490407

Bjørn Kjos-Hanssen, Kayleigh K. Hyde

Publication date: 27 August 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

combinatorics on wordsnondeterministic finite automataalmost square-free wordsautomatic complexitystrongly cube-free words

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (8)

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ On the complexity of automatic complexity ⋮ The Complexity of Complexity ⋮ Automatic complexity of Fibonacci and tribonacci words ⋮ An incompressibility theorem for automatic complexity ⋮ Few Paths, Fewer Words: Model Selection With Automatic Structure Functions ⋮ Automatic complexity of shift register sequences ⋮ VC-dimensions of nondeterministic finite automata for words of equal length

Cites Work

• Unnamed Item
• Thue-Morse at multiples of an integer
• Finite state complexity
• The equation \(a_ M=b^ Nc^ P\) in a free group
• How many squares must a binary sequence contain?
• Chains and fixing blocks in irreducible binary sequences
• Algorithmic Randomness and Complexity
• A Second Course in Formal Languages and Automata Theory
• Sur les nombres qui ont des propriétés additives et multiplicatives données

This page was built for publication: Nondeterministic automatic complexity of overlap-free and almost square-free words