On non-determinacy in simple computing devices
From MaRDI portal
Publication:2550291
DOI10.1007/BF00289513zbMath0229.68014MaRDI QIDQ2550291
Publication date: 1972
Published in: Acta Informatica (Search for Journal in Brave)
Related Items
One-way reversible multi-head finite automata ⋮ Logarithmic space and permutations ⋮ Finite dP Automata versus Multi-head Finite Automata ⋮ PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS ⋮ One-Way Reversible Multi-head Finite Automata ⋮ The equivalence of pebbles and sensing heads for finite automata ⋮ Hierarchies of one-way multihead automata languages ⋮ Cyclic automata ⋮ Multiprocessor automata ⋮ Unnamed Item ⋮ Alternating multihead finite automata ⋮ A new complete language for DSPACE(log n) ⋮ Descriptive characterizations of computational complexity ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Unnamed Item ⋮ On two-way weak counter machines ⋮ Three-way two-dimensional multicounter automata ⋮ Tight hierarchy of data-independent multi-head automata ⋮ Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata ⋮ On multi-head automata with restricted nondeterminism ⋮ Fooling a two way automaton or one pushdown store is better than one counter for two way machines ⋮ Computing on structures ⋮ The complexity of debate checking ⋮ Multihead two-way probabilistic finite automata ⋮ Relativization of questions about log space computability ⋮ PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES ⋮ Ramified Corecurrence and Logspace ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages ⋮ Some results concerning automata on two-dimensional tapes ⋮ On tape-bounded complexity classes and multihead finite automata ⋮ Rudimentary relations and stack languages ⋮ Marker automata ⋮ Properties of probabilistic pushdown automata ⋮ Returning and non-returning parallel communicating finite automata are equivalent ⋮ Relating refined space complexity classes ⋮ Unnamed Item ⋮ Multihead two-way probabilistic finite automata ⋮ Primitive recursion in the abstract ⋮ Diving into the queue ⋮ Properties of probabilistic pushdown automata ⋮ A note on multihead automata and context-sensitive languages ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ Context-free languages can be accepted with absolutely no space overhead ⋮ Some undecidable problems for parallel communicating finite automata systems ⋮ Amplification of slight probabilistic advantage at absolutely no cost in space ⋮ Multi-head finite automata: Data-independent versus data-dependent computations
Cites Work
