On the Tape Complexity of Deterministic Context-Free Languages
From MaRDI portal
Publication:4158497
DOI10.1145/322077.322083zbMath0379.68054OpenAlexW1979328074MaRDI QIDQ4158497
Publication date: 1978
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322077.322083
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)
Related Items (60)
Alternating and empty alternating auxiliary stack automata. ⋮ Pattern selector grammars and several parsing algorithms in the context- free style ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Branching Programs for Tree Evaluation ⋮ Self-reducibility ⋮ A PTIME-complete matching problem for SLP-compressed words ⋮ Complexity of boundary graph languages ⋮ On the relative complexity of some languages in \(NC^ 1\) ⋮ Some modifications of auxiliary pushdown automata ⋮ Growing context-sensitive languages and Church-Rosser languages ⋮ Reversals and alternation ⋮ On weak growing context-sensitive grammars ⋮ Empty alternation ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata ⋮ McNaughton families of languages. ⋮ Tree-size bounded alternation ⋮ Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract) ⋮ Bounded tree-width and LOGCFL ⋮ Sweeping input-driven pushdown automata ⋮ On the complexity of regular-grammars with integer attributes ⋮ Knapsack in graph groups ⋮ Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ Upper and lower bounds for first order expressibility ⋮ The complexity of short two-person games ⋮ An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic ⋮ Properties that characterize LOGCFL ⋮ Unnamed Item ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Nonuniform complexity and the randomness of certain complete languages ⋮ Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Multihead two-way probabilistic finite automata ⋮ Interactive proof systems and alternating time-space complexity ⋮ Extensions to Barrington's M-program model ⋮ Unambiguity of circuits ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ The intractability of computing the Hamming distance ⋮ The descriptive complexity approach to LOGCFL ⋮ String shuffle: circuits and graphs ⋮ On relativizing auxiliary pushdown machines ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Properties of probabilistic pushdown automata ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ The complexity of graph languages generated by hyperedge replacement ⋮ On inverse deterministic pushdown transductions ⋮ Knapsack in hyperbolic groups ⋮ On growing context-sensitive languages ⋮ Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Prediction-preserving reducibility ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Properties of probabilistic pushdown automata ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Time and space complexity of inside-out macro languages ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ Restricted CRCW PRAMs
This page was built for publication: On the Tape Complexity of Deterministic Context-Free Languages
