Real-time computations with restricted nondeterminism

DOI10.1007/BF01776575zbMath0409.68027MaRDI QIDQ4197340

Patrick C. Fischer, Chandra M. R. Kintala

Publication date: 1979

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

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)

Related Items

Regulated nondeterminism in pushdown automata ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ Context-dependent nondeterminism for pushdown automata ⋮ The emptiness problem for intersections of regular languages ⋮ Regulated Nondeterminism in Pushdown Automata ⋮ Self-verifying Cellular Automata ⋮ Shrinking one-way cellular automata ⋮ On multi-head automata with restricted nondeterminism ⋮ Self-Verifying Pushdown and Queue Automata ⋮ Computational power of one-way Turing machines with sublogarithmic memory restrictions ⋮ Iterative arrays with self-verifying communication cell ⋮ Complexity of One-Way Cellular Automata ⋮ Measuring nondeterminism in pushdown automata ⋮ Non-deterministic cellular automata and languages ⋮ Nondeterministics circuits, space complexity and quasigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Computational Complexity of Algorithms
• Turing machines with restricted memory access
• Real-Time Definable Languages
• Quasi-realtime languages
• Classes of languages and linear-bounded automata
• The complexity of theorem-proving procedures
• Real-Time Simulation of Multihead Tape Units