Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
From MaRDI portal
Publication:5626625
DOI10.1145/321623.321625zbMath0222.02035OpenAlexW2079275582MaRDI QIDQ5626625
Publication date: 1971
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321623.321625
Related Items (only showing first 100 items - show all)
Alternating and empty alternating auxiliary stack automata. ⋮ Two-way automata with more than one storage medium ⋮ On the Complexity of Intersecting Regular, Context-Free, and Tree Languages ⋮ Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) ⋮ Some observations concerning alternating Turing machines using small space ⋮ Hierarchies of one-way multihead automata languages ⋮ Self-reducibility ⋮ Sufficient-completeness, ground-reducibility and their complexity ⋮ Some relationships between logics of programs and complexity theory ⋮ A PTIME-complete matching problem for SLP-compressed words ⋮ k\(+1\) heads are better than k for PDAs ⋮ Relativized alternation and space-bounded computation ⋮ Pushdown automata with reversal-bounded counters ⋮ Reachability in pushdown register automata ⋮ Alternating multihead finite automata ⋮ Complexity theory of parallel time and hardware ⋮ Some modifications of auxiliary pushdown automata ⋮ The subpower membership problem for bands ⋮ Generalized satisfiability for the description logic \(\mathcal{ALC}\) ⋮ A near-optimal method for reasoning about action ⋮ A simulation result for the auxiliary pushdown automata ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Program Schemes with Deep Pushdown Storage ⋮ Tree-size bounded alternation ⋮ Analysing the implicit complexity of programs. ⋮ P-hardness of the emptiness problem for visibly pushdown languages ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ On uniform circuit complexity ⋮ Complexity of algorithms and computations ⋮ Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata ⋮ The complexity of regular DNLC graph languages ⋮ 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 ⋮ The Power of Non-determinism in Higher-Order Implicit Complexity ⋮ Incremental branching programs ⋮ An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic ⋮ Properties that characterize LOGCFL ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Iterated stack automata and complexity classes ⋮ Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Relativization of questions about log space computability ⋮ PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES ⋮ Relationships between pushdown automata with counters and complexity classes ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Unambiguity of circuits ⋮ Recursive turing machines † ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Quasi-interpretations. A way to control resources ⋮ Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages ⋮ The complexity of ranking simple languages ⋮ An observation on time-storage trade off ⋮ The intractability of computing the Hamming distance ⋮ 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 ⋮ On relativizing auxiliary pushdown machines ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ The complexity of propositional implication ⋮ A recursive and a grammatical characterization of the exponential-time languages ⋮ On inverse deterministic pushdown transductions ⋮ Hierarchies of recursive computations† ⋮ A relation between space, return and dual return complexities ⋮ Unary Resolution: Characterizing Ptime ⋮ Tradeoff lower lounds for stack machines ⋮ The power of two-way deterministic checking stack automata ⋮ Turing machines with access to history ⋮ On Models of a Nondeterministic Computation ⋮ A multiparameter analysis of the boundedness problem for vector addition systems ⋮ Boundedness, empty channel detection, and synchronization for communicating finite automata ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Properties of probabilistic pushdown automata ⋮ A Practical Simulation Result for Two-Way Pushdown Automata ⋮ Semantics and expressiveness issues in active databases ⋮ Positive versions of polynomial time ⋮ Pushdown automata with counters ⋮ On the power of deep pushdown stacks ⋮ Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata ⋮ On two-way multihead automata ⋮ Time and space complexity of inside-out macro languages ⋮ A note on self-modifying finite automata ⋮ Theory of formal grammars ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ Generation problems ⋮ The complexity of monadic recursion schemes: Exponential time bounds ⋮ String distances and intrusion detection: Bridging the gap between formal languages and computer security ⋮ How hard is computing the edit distance? ⋮ Computing a context-free grammar-generating series ⋮ Deterministic two-way one-head pushdown automata are very powerful ⋮ Consistency in nondeterministic storage ⋮ Some undecidable problems for parallel communicating finite automata systems ⋮ Notes on looping deterministic two-way pushdown automata ⋮ The complexity of computing maximal word functions ⋮ Random Generation for Finitely Ambiguous Context-free Languages ⋮ Logical and schematic characterization of complexity classes ⋮ Parallel random access machines with powerful instruction sets ⋮ (Semi)alternating stack automata
This page was built for publication: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
