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
PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS, How hard is to compute the edit distance, Unnamed Item, Unnamed Item, Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures, Reversals and alternation, Empty alternation, New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines, On the complexity of decision problems for some classes of machines and applications, Generalizations of Checking Stack Automata: Characterizations and Hierarchies, Generalizing Cook's transformation to imperative stack programs, Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract), Unnamed Item, ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM, Some results concerning automata on two-dimensional tapes, Inclusion complete tally languages and the Hartmanis-Berman conjecture, The descriptive complexity approach to LOGCFL, Properties of probabilistic pushdown automata, Computing LOGCFL certificates, Unnamed Item, 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, Nonuniform complexity classes specified by lower and upper bounds, Turing machines and the spectra of first-order formulas, 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
