scientific article; zbMATH DE number 3984575

MaRDI QIDQ3747727zbMATH OpenFDO

Authors M. Ya. Alberts

Publication date 1985

zbMATH Keywords

Nondeterministic Turing machinesregular languagespace complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3982519
• scientific article; zbMATH DE number 18635
• Two Tapes are Better than One for Nondeterministic Machines
• scientific article; zbMATH DE number 3917711
• On the structure of one-tape nondeterministic Turing machine time hierarchy

Cited in

(32)

• Remarks on languages acceptable in log log n space
• An NP-complete language accepted in linear time by a one-tape Turing machine
• A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space
• A note on multi-inkdot nondeterministic Turing machines with small space
• Nondeterministic stack register machines
• Element distinctness on one-tape Turing machines: a complete solution
• Restricted Turing machines and language recognition
• Mirror images and schemes for the maximal complexity of nondeterminism
• Deciding according to the shortest computations
• scientific article; zbMATH DE number 3883610 (Why is no real title available?)
• scientific article; zbMATH DE number 3887666 (Why is no real title available?)
• scientific article; zbMATH DE number 3856412 (Why is no real title available?)
• Two Tapes are Better than One for Nondeterministic Machines
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Single-tape reset machines
• scientific article; zbMATH DE number 3976379 (Why is no real title available?)
• scientific article; zbMATH DE number 3980489 (Why is no real title available?)
• scientific article; zbMATH DE number 3982519 (Why is no real title available?)
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• scientific article; zbMATH DE number 3988711 (Why is no real title available?)
• scientific article; zbMATH DE number 4045156 (Why is no real title available?)
• scientific article; zbMATH DE number 18635 (Why is no real title available?)
• scientific article; zbMATH DE number 3581615 (Why is no real title available?)
• scientific article; zbMATH DE number 1222596 (Why is no real title available?)
• scientific article; zbMATH DE number 2040917 (Why is no real title available?)
• scientific article; zbMATH DE number 2068877 (Why is no real title available?)
• scientific article; zbMATH DE number 5593330 (Why is no real title available?)
• Complexity of nondeterministic multitape computations based on crossing sequences
• Deterministic simulation of non-deterministic Turing machines (detailed abstract)
• Logical Approaches to Computational Barriers
• Turing machines with access to history
• A note on off-line machines with 'Brownian' input heads

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