Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
From MaRDI portal
Publication:4128015
Cites work
- scientific article; zbMATH DE number 3471606 (Why is no real title available?)
- scientific article; zbMATH DE number 3478425 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 3557270 (Why is no real title available?)
- scientific article; zbMATH DE number 3640911 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Bounded-reversal multihead finite automata languages
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Classes of languages and linear-bounded automata
- Depth-First Search and Linear Graph Algorithms
- On Languages Accepted in Polynomial Time
- On non-determinacy in simple computing devices
- On tape-bounded complexity classes and multihead finite automata
- On the Computational Complexity of Algorithms
- On two-way multihead automata
- Relationships between nondeterministic and deterministic tape complexities
- The complexity of theorem-proving procedures
- Three theorems on phrase structure grammars of type 1
- Time and tape complexity of pushdown automaton languages
- Two-way pushdown automata
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)
