scientific article; zbMATH DE number 3403734

zbMath0255.68015MaRDI QIDQ5670175

Stephen A. Cook

Publication date: 1972

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

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

Related Items (21)

Refined simulation of multihead automata ⋮ Maximally-Polyvariant Partial Evaluation in Polynomial Time ⋮ On the language of primitive words ⋮ Unnamed Item ⋮ Alternating multihead finite automata ⋮ New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines ⋮ Searching for Gapped Palindromes ⋮ Generalizing Cook's transformation to imperative stack programs ⋮ Parallel detection of all palindromes in a string ⋮ Partial memoization for obtaining linear time behavior of a 2DPDA ⋮ A V log V algorithm for isomorphism of triconnected planar graphs ⋮ Window-accumulated subsequence matching problem is linear ⋮ A note on linear time simulation of deterministic two-way pushdown automata ⋮ Computational complexity of multitape Turing machines and random access machines ⋮ Dynamic interpolation search revisited ⋮ A Practical Simulation Result for Two-Way Pushdown Automata ⋮ Searching for gapped palindromes ⋮ A simulation result for two-way pushdown automata ⋮ Time bounded random access machines ⋮ On efficient recognition of transductions and relations ⋮ Three one-way heads cannot do string matching

This page was built for publication: