On the computational complexity of infinite words

DOI10.1007/3-540-44683-4_29MaRDI QIDQ4779155zbMATH OpenFDO

Authors Pavol Ďuriš, Ján Maňuch

Publication date 25 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2136/21360328

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Recommendations

• On the computational complexity of infinite words.
• On the minimal complexity of infinite words
• On a new notion of complexity on infinite words
• The Kolmogorov complexity of infinite words
• On additive complexity of infinite words
• scientific article; zbMATH DE number 4057009
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Bounds on the Kolmogorov complexity function for infinite words
• Initial non-repetitive complexity of infinite words

Cited in

(10)

• On the computational complexity of infinite words.
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• ON THE REPETITIVITY INDEX OF INFINITE WORDS
• On Turing's formula for word probabilities
• scientific article; zbMATH DE number 4057009 (Why is no real title available?)
• scientific article; zbMATH DE number 7559499 (Why is no real title available?)
• Parallel complexity of iterated morphisms and the arithmetic of small numbers
• scientific article; zbMATH DE number 7069796 (Why is no real title available?)
• Proof of a conjecture on word complexity
• Comparing descriptional and computational complexity of infinite words

This page was built for publication: On the computational complexity of infinite words

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