scientific article; zbMATH DE number 4057009

zbMATH Open0647.68050MaRDI QIDQ3792243FDOQ3792243

Authors: Daina Taimina 

Publication date: 1987

Title of this publication is not available (Why is that?)

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

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)

Cited In (5)

• Title not available (Why is that?)
• Geometric problems on two-dimensional array processors
• Title not available (Why is that?)
• On Turing's formula for word probabilities
• Infinite Computations and a Hierarchy in  3 Reconsidered

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)