Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages

Cites Work

On the Computational Complexity of Algorithms
Two-way pushdown automata
Depth-First Search and Linear Graph Algorithms
Relationships between nondeterministic and deterministic tape complexities
The complexity of theorem-proving procedures
On non-determinacy in simple computing devices
Title not available (Why is that?)
Title not available (Why is that?)
Time and tape complexity of pushdown automaton languages
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
On tape-bounded complexity classes and multihead finite automata
Bounded-reversal multihead finite automata languages
Title not available (Why is that?)
Title not available (Why is that?)
Classes of languages and linear-bounded automata
On two-way multihead automata
On Languages Accepted in Polynomial Time
Three theorems on phrase structure grammars of type 1
Title not available (Why is that?)
Title not available (Why is that?)

Cited In (13)

A simple P-complete problem and its language-theoretic representations
Language recognition by two-way deterministic pushdown automata
Deterministic two-way one-head pushdown automata are very powerful
Alternating multihead finite automata
Some properties of one-pebble Turing machines with sublogarithmic space
One-way simple multihead finite automata
Hierarchies of one-way multihead automata languages
A hardest language recognized by two-way nondeterministic pushdown automata
Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata
Time complexity of languages recognized by one-way multihead pushdown automata
Variations on the technique of Ďuriš and Galil
Fooling a two way automaton or one pushdown store is better than one counter for two way machines
Two-way deterministic multi-weak-counter machines

This page was built for publication: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages

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