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

DOI10.1007/BF01683273zbMath0356.68064MaRDI QIDQ4128015

Zvi Galil

Publication date: 1977

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

Mathematics Subject Classification ID

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

Related Items (13)

Hierarchies of one-way multihead automata languages ⋮ Alternating multihead finite automata ⋮ A simple P-complete problem and its language-theoretic representations ⋮ 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 ⋮ A hardest language recognized by two-way nondeterministic pushdown automata ⋮ 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 ⋮ One-way simple multihead finite automata ⋮ Some properties of one-pebble Turing machines with sublogarithmic space ⋮ Language recognition by two-way deterministic pushdown automata ⋮ Deterministic two-way one-head pushdown automata are very powerful ⋮ Variations on the technique of Ďuriš and Galil

Cites Work

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

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