Real-time computations with restricted nondeterminism

DOI10.1007/BF01776575MaRDI QIDQ4197340zbMATH OpenFDO

Authors Patrick C. Fischer, Chandra M. R. Kintala

Publication date 1979

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01776575

zbMATH Keywords

Computational ComplexityLanguages Acceptable By Real-Time Multitape Turing MachinesReal-Time Definable Languages

Mathematics Subject Classification ID

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

Cites work

• Classes of languages and linear-bounded automata
• scientific article; zbMATH DE number 3495593 (Why is no real title available?)
• scientific article; zbMATH DE number 3201659 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• On the Computational Complexity of Algorithms
• Quasi-realtime languages
• Real-Time Definable Languages
• Real-Time Simulation of Multihead Tape Units
• The complexity of theorem-proving procedures
• Turing machines with restricted memory access

Cited in

(15)

• Nondeterministics circuits, space complexity and quasigroups
• Computational power of one-way Turing machines with sublogarithmic memory restrictions
• Measuring nondeterminism in pushdown automata
• Non-deterministic cellular automata and languages
• In memoriam Chandra Kintala
• Regulated Nondeterminism in Pushdown Automata
• On multi-head automata with restricted nondeterminism
• The emptiness problem for intersections of regular languages
• Self-verifying pushdown and queue automata
• Complexity of one-way cellular automata
• Self-verifying Cellular Automata
• Shrinking one-way cellular automata
• Iterative arrays with self-verifying communication cell
• Regulated nondeterminism in pushdown automata
• Context-dependent nondeterminism for pushdown automata

This page was built for publication: Real-time computations with restricted nondeterminism

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