scientific article; zbMATH DE number 3903969

MaRDI QIDQ3681938zbMATH OpenFDO

Authors Giancarlo Mauri, Alberto Bertoni, N. Sabadini

Publication date 1984

zbMATH Keywords

alternating Turing machinescounting Turing machinesdecision problemsenumeration problemsnondeterministic Turing machinesRandom Access Machines

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)

Recommendations

• On non-determinism in machines and languages
• Nondeterministic multicounter machines and complementation
• Non-deterministic structures of computation
• Deterministic realizations of nondeterministic automata
• scientific article; zbMATH DE number 4021119
• scientific article; zbMATH DE number 4024793
• scientific article; zbMATH DE number 3982519
• scientific article; zbMATH DE number 6125212
• scientific article; zbMATH DE number 4045156
• On Models of a Nondeterministic Computation

Cited in

(19)

• On nondeterminism in parallel computation
• Theory of traces
• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• On non-determinism in machines and languages
• Nondeterministic stack register machines
• Counting nondeterministic computations
• A nondeterministic Turing machine variant to compute functions
• Deciding according to the shortest computations
• Unconventional “Stateless” Turing–Like Machines
• scientific article; zbMATH DE number 4021119 (Why is no real title available?)
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• scientific article; zbMATH DE number 4045156 (Why is no real title available?)
• scientific article; zbMATH DE number 176517 (Why is no real title available?)
• scientific article; zbMATH DE number 3581615 (Why is no real title available?)
• scientific article; zbMATH DE number 1285798 (Why is no real title available?)
• scientific article; zbMATH DE number 6125212 (Why is no real title available?)
• Remembering Chandra Kintala
• Non-erasing turing machines: A new frontier between a decidable halting problem and universality
• Logical Approaches to Computational Barriers

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