scientific article; zbMATH DE number 4145886

zbMATH Open0699.03021MaRDI QIDQ3476799FDOQ3476799

Authors: Kenneth McAloon 

Publication date: 1990

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

Recommendations

• scientific article; zbMATH DE number 2068877
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• New time hierarchy results for deterministic TMS
• Towards separating nondeterminism from determinism
• Deterministic Turing machines in the range between real-time and linear-time.

zbMATH Keywords

hierarchy theoremmulti-tape Turing machinesdeterministic modemixed timenondeterministic mode

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Cited In (4)

• New time hierarchy results for deterministic TMS
• Title not available (Why is that?)
• Tighter constant-factor time hierarchies
• On average time hierarchies

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 Q3476799)