On the public citation graph
Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
0 signed · 62 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1007/bf00289513openalex-snapshot
On non-determinancy in simple computing devices
inferredcites →https://doi.org/10.1016/s0019-9958(63)90169-4openalex-snapshot
Three theorems on phrase structure grammars of type 1
inferredcites →https://doi.org/10.1016/s0019-9958(64)90120-2openalex-snapshot
Classes of languages and linear-bounded automata
inferredcites →https://doi.org/10.1016/s0019-9958(67)90369-5openalex-snapshot
Two-way pushdown automata
inferredcites →https://doi.org/10.1016/s0019-9958(68)91087-5openalex-snapshot
Time and tape complexity of pushdown automaton languages
inferredcites →https://doi.org/10.1016/s0019-9958(74)90994-2openalex-snapshot
Bounded-reversal multihead finite automata languages
inferredcites →https://doi.org/10.1016/s0022-0000(70)80006-xopenalex-snapshot
Relationships between nondeterministic and deterministic tape complexities
inferredcites →https://doi.org/10.1016/s0022-0000(73)80048-0openalex-snapshot
On two-way multihead automata
inferredcites →https://doi.org/10.1016/s0022-0000(75)80014-6openalex-snapshot
On tape-bounded complexity classes and multihead finite automata
inferredcites →https://doi.org/10.1090/s0002-9947-1965-0170805-7openalex-snapshot
On the Computational Complexity of Algorithms
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/focs.1965.11openalex-snapshot
Hierarchies of memory limited computations
inferredcites →https://doi.org/10.1109/focs.1965.14openalex-snapshot
Memory bounds for recognition of context-free and context-sensitive languages
inferredcites →https://doi.org/10.1109/sfcs.1975.23openalex-snapshot
On time versus space and related problems
inferredcites →https://doi.org/10.1137/0201010openalex-snapshot
Depth-First Search and Linear Graph Algorithms
inferredcites →https://doi.org/10.1137/0201019openalex-snapshot
On Languages Accepted in Polynomial Time
inferredcites →https://doi.org/10.1145/321623.321625openalex-snapshot
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
inferredcites →https://doi.org/10.1145/800119.803882openalex-snapshot
Storage requirements for deterministic / polynomial time recognizable languages
inferredcites →https://doi.org/10.1145/800119.803883openalex-snapshot
Complete problems for deterministic polynomial time
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1145/800125.804030openalex-snapshot
On the time and tape complexity of languages I
inferredcites →https://doi.org/10.1145/800125.804032openalex-snapshot
An observation on time-storage trade off
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.13182/nse70-a19706openalex-snapshot
Formal Languages and their Relation to Automata
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/3-540-10843-2_40openalex-snapshot
Alternating multihead finite automata
inferred← citeshttps://doi.org/10.1007/3-540-13345-3_22openalex-snapshot
Space and time efficient simulations and characterizations of some restricted classes of PDAS
inferred← citeshttps://doi.org/10.1007/3-540-16761-7_49openalex-snapshot
Characterizations of PUNC and precomputation
inferred← citeshttps://doi.org/10.1007/3-540-60044-2_50openalex-snapshot
New results and open problems related to non-standard stringology
inferred← citeshttps://doi.org/10.1007/978-3-030-89543-3_14openalex-snapshot
Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
inferred← citeshttps://doi.org/10.1007/978-3-540-24587-2_65openalex-snapshot
Some Properties of One-Pebble Turing Machines with Sublogarithmic Space
inferred← citeshttps://doi.org/10.1007/978-3-540-74593-8_23openalex-snapshot
A Simple P-Complete Problem and Its Representations by Language Equations
inferred← citeshttps://doi.org/10.1007/978-3-642-82456-2_24openalex-snapshot
The Complexity of Two-Way Pushdown Automata and Recursive Programs
inferred← citeshttps://doi.org/10.1007/bfb0012766openalex-snapshot
On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
inferred← citeshttps://doi.org/10.1007/bfb0030304openalex-snapshot
Nondeterminism is essential for two-way counter machines
inferred← citeshttps://doi.org/10.1007/s10559-005-0034-7openalex-snapshot
Language recognition by two-way deterministic pushdown automata
inferred← citeshttps://doi.org/10.1016/0020-0190(81)90044-2openalex-snapshot
Time complexity of languages recognized by one-way multihead pushdown automata
inferred← citeshttps://doi.org/10.1016/0020-0190(81)90045-4openalex-snapshot
A hardest language recognized by two-way nondeterministic pushdown automata
inferred← citeshttps://doi.org/10.1016/0020-0190(84)90001-2openalex-snapshot
Deterministic two-way one-head pushdown automata are very powerful
inferred← citeshttps://doi.org/10.1016/0304-3975(79)90033-1openalex-snapshot
One-way simple multihead finite automata
inferred← citeshttps://doi.org/10.1016/0304-3975(82)90086-xopenalex-snapshot
Two-way deterministic multi-weak-counter machines
inferred← citeshttps://doi.org/10.1016/0304-3975(82)90087-1openalex-snapshot
Fooling a two way automation or one pushdown store is better than one counter for two way machines
inferred← citeshttps://doi.org/10.1016/0304-3975(86)90093-9openalex-snapshot
Hierarchies of one-way multihead automata languages
inferred← citeshttps://doi.org/10.1016/0304-3975(88)90122-3openalex-snapshot
Alternating multihead finite automata
inferred← citeshttps://doi.org/10.1016/b978-0-12-115350-2.50015-4openalex-snapshot
THE INTERFACE BETWEEN LANGUAGE THEORY AND COMPLEXITY THEORY11Preparation of this paper was supported in part by the National Science Foundation under Grant No. MCS79-04012.
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.04.003openalex-snapshot
Some properties of one-pebble Turing machines with sublogarithmic space
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.09.015openalex-snapshot
A simple P-complete problem and its language-theoretic representations
inferred← citeshttps://doi.org/10.1016/s0019-9958(82)80023-5openalex-snapshot
On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
inferred← citeshttps://doi.org/10.1016/s0019-9958(85)80029-2openalex-snapshot
Some characterizations of multihead finite automata
inferred← citeshttps://doi.org/10.1016/s0019-9958(85)80030-9openalex-snapshot
On space and time efficient TM simulations of some restricted classes of PDA's
inferred← citeshttps://doi.org/10.1080/23799927.2023.2166872openalex-snapshot
Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata
inferred← citeshttps://doi.org/10.1109/ic-cgu67042.2025.11338068openalex-snapshot
Dynamic Gaming Systems Powered by Automata Theory: A Case Study of Maze Raiders:Quest for glory
inferred← citeshttps://doi.org/10.1109/swat.1974.29openalex-snapshot
Two way deterministic pushdown automaton languages and some open problems in the theory of computation
inferred← citeshttps://doi.org/10.1137/s0097539796298339openalex-snapshot
On the Structure of Logspace Probabilistic Complexity Classes
inferred← citeshttps://doi.org/10.1142/s0218001499000306openalex-snapshot
SPACE HIERARCHIES OF TWO-DIMENSIONAL ALTERNATING TURING MACHINES, PUSHDOWN AUTOMATA AND COUNTER AUTOMATA
inferred← citeshttps://doi.org/10.1145/3498702openalex-snapshot
Subcubic certificates for CFL reachability
inferred← citeshttps://doi.org/10.1145/800076.802471openalex-snapshot
Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version)
inferred← citeshttps://doi.org/10.25596/jalc-2007-097openalex-snapshot
Two-Way Finite Automata with a Write-Once Track
inferred← citeshttps://doi.org/10.48550/arxiv.2108.12779openalex-snapshot
Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL$\subseteq$LOGDCFL/poly Question
inferred← citeshttps://doi.org/10.5860/choice.33-3959openalex-snapshot
Limits to parallel computation: P-completeness theory
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.