scientific article; zbMATH DE number 4057009

MaRDI QIDQ3792243zbMATHFDO

Authors Daina Taimina

Publication date 1987

zbMATH Keywords

computational complexitycomplexity measuresprobabilistic automataregular languages\(\omega \)-languagenon-regular languagescomplexity gaps of Turing machines on finite wordsdeterministic filter \(\omega \)-automatoninfinite input words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1834659
• On the computational complexity of infinite words.
• On a new notion of complexity on infinite words
• On the minimal complexity of infinite words
• The Kolmogorov complexity of infinite words
• The Length of Infinite Time Turing Machine Computations
• Bounds on the Kolmogorov complexity function for infinite words
• On additive complexity of infinite words
• Space and time complexity for infinite time Turing machines
• On the complexity of infinite sequences

Cited in

(5)

• Infinite Computations and a Hierarchy in  3 Reconsidered
• scientific article; zbMATH DE number 18627 (Why is no real title available?)
• scientific article; zbMATH DE number 1834659 (Why is no real title available?)
• Geometric problems on two-dimensional array processors
• On Turing's formula for word probabilities

This page was built for publication:

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