Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

Cited in

(only showing first 100 items - show all)

On the power of deep pushdown stacks
Remarks on multihead pushdown automata and multihead stack automata
Consistency in nondeterministic storage
Two-way automata with more than one storage medium
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
Some observations concerning alternating Turing machines using small space
Hierarchies of one-way multihead automata languages
Some relationships between logics of programs and complexity theory
k\(+1\) heads are better than k for PDAs
Relativized alternation and space-bounded computation
Pushdown automata with reversal-bounded counters
Alternating multihead finite automata
Complexity theory of parallel time and hardware
A near-optimal method for reasoning about action
A simulation result for the auxiliary pushdown automata
Tree-size bounded alternation
On uniform circuit complexity
Complexity of algorithms and computations
On the time and tape complexity of weak unification
Fooling a two way automaton or one pushdown store is better than one counter for two way machines
Symmetric space-bounded computation
Properties that characterize LOGCFL
Iterated stack automata and complexity classes
Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
Unambiguity of circuits
An observation on time-storage trade off
Translational lemmas, polynomial time, and \((\log n)^j\)-space
Two-way nested stack automata are equivalent to two-way stack automata
Comparing complexity classes
Remarks on the complexity of nondeterministic counter languages
A recursive and a grammatical characterization of the exponential-time languages
On inverse deterministic pushdown transductions
A relation between space, return and dual return complexities
Non-commutative arithmetic circuits: depth reduction and size lower bounds
Properties of probabilistic pushdown automata
Semantics and expressiveness issues in active databases
Positive versions of polynomial time
Notes on looping deterministic two-way pushdown automata
The complexity of computing maximal word functions
Logical and schematic characterization of complexity classes
Analysing the implicit complexity of programs.
A note on self-modifying finite automata
Some undecidable problems for parallel communicating finite automata systems
The subpower membership problem for bands
The power of two-way deterministic checking stack automata
A multiparameter analysis of the boundedness problem for vector addition systems
Boundedness, empty channel detection, and synchronization for communicating finite automata
Theory of formal grammars
How hard is computing the edit distance?
Computing a context-free grammar-generating series
Alternating and empty alternating auxiliary stack automata.
P-hardness of the emptiness problem for visibly pushdown languages
Small space analogues of Valiant's classes and the limitations of skew formulas
Data independence of read, write, and control structures in PRAM computations
Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
A PTIME-complete matching problem for SLP-compressed words
Reachability in pushdown register automata
Pushdown automata with counters
Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
On two-way multihead automata
Generation problems
Self-reducibility
Sufficient-completeness, ground-reducibility and their complexity
Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-k storage automata
Unary resolution: characterizing \textsc{Ptime}
A practical simulation result for two-way pushdown automata
The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
The complexity of ranking simple languages
Random Generation for Finitely Ambiguous Context-free Languages
On Models of a Nondeterministic Computation
String distances and intrusion detection: Bridging the gap between formal languages and computer security
On the complexity of intersecting regular, context-free, and tree languages
Some modifications of auxiliary pushdown automata
Complexity and Algorithms for Well-Structured k-SAT Instances
Program Schemes with Deep Pushdown Storage
Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
On relativizing auxiliary pushdown machines
Hierarchies of recursive computations†
Time and space complexity of inside-out macro languages
Generalized satisfiability for the description logic \(\mathcal{ALC}\)
Parallel random access machines with powerful instruction sets
(Semi)alternating stack automata
Relativization of questions about log space computability
Relationships between pushdown automata with counters and complexity classes
On the complexity of finite, pushdown, and stack automata
Recursive turing machines †
Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
scientific article; zbMATH DE number 3560777 (Why is no real title available?)
Some results concerning automata on two-dimensional tapes
Inclusion complete tally languages and the Hartmanis-Berman conjecture
scientific article; zbMATH DE number 3576701 (Why is no real title available?)
The complexity of the membership problem for some extensions of context-free languagest†
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS
scientific article; zbMATH DE number 6917940 (Why is no real title available?)
ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
Nonuniform complexity classes specified by lower and upper bounds
An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
Turing machines and the spectra of first-order formulas

This page was built for publication: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

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