Tree-size bounded alternation

DOI10.1016/0022-0000(80)90036-7zbMath0445.68034OpenAlexW1965022641MaRDI QIDQ1145502

Walter L. Ruzzo

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(80)90036-7

zbMATH Keywords

pushdown automataalternating Turing machinecontext-free language recognitionaccepting computation treelanguages log-space-reducible to context-free languagestree-size bounded alternation

Mathematics Subject Classification ID

Related Items (77)

On 1-inkdot alternating Turing machines with small space ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Alternating on-line Turing machines with only universal states and small space bounds ⋮ Parallel pointer machines ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs ⋮ On the complexity of parallel parsing of general context-free languages ⋮ Parallel time O(log n) recognition of unambiguous context-free languages ⋮ Parallel complexity of logical query programs ⋮ Expressing uniformity via oracles ⋮ Decompositions of nondeterministic reductions ⋮ A parallelizable lexicographically first maximal edge-induced subgraph problem ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs ⋮ Complexity theory of parallel time and hardware ⋮ Unnamed Item ⋮ Constructions for alternating finite automata^∗ ⋮ Complexity of boundary graph languages ⋮ Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs ⋮ On the relationship of congruence closure and unification ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Growing context-sensitive languages and Church-Rosser languages ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ Reversals and alternation ⋮ On weak growing context-sensitive grammars ⋮ Parallel recognition and ranking of context-free languages ⋮ Subclasses of \textsc{Ptime} interpreted by programming languages ⋮ From bidirectionality to alternation. ⋮ Tree-size bounded alternation ⋮ Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract) ⋮ Bounded tree-width and LOGCFL ⋮ On the complexity of regular-grammars with integer attributes ⋮ On uniform circuit complexity ⋮ Pebbling with an auxiliary pushdown ⋮ Two-way automata and length-preserving homomorphisms ⋮ The complexity of short two-person games ⋮ Properties that characterize LOGCFL ⋮ Iterated stack automata and complexity classes ⋮ Succinct certification of monotone circuits ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Upper bounds on recognition of a hierarchy of non-context-free languages ⋮ Relating attribute grammars and lexical-functional grammars ⋮ Parallel parsing of tree adjoining grammars on the connection machine ⋮ An NC algorithm for recognizing tree adjoining languages ⋮ Extensions to Barrington's M-program model ⋮ Unambiguity of circuits ⋮ Hypertree decompositions and tractable queries ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ The complexity of ranking simple languages ⋮ Finite graph automata for linear and boundary graph languages ⋮ Unnamed Item ⋮ 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 ⋮ Two dynamic programming algorithms for which interpreted pebbling helps ⋮ The complexity of graph languages generated by hyperedge replacement ⋮ Computing LOGCFL certificates ⋮ Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Tradeoff lower lounds for stack machines ⋮ Effective entropies and data compression ⋮ Systolic parsing of context-free languages ⋮ Properties of probabilistic pushdown automata ⋮ A leaf-time hierarchy of two-dimensional alternating turing machines ⋮ On efficient parallel computations of costs of paths on a grid graph ⋮ Linear graph grammars: Power and complexity ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ A note on alternating on-line Turing machines ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ Two-dimensional alternative Turing machines ⋮ Alternating simple multihead finite automata ⋮ Restricted CRCW PRAMs ⋮ On the parallel recognition of unambiguous context-free languages ⋮ On the complexity of the recognition of parallel 2D-image languages ⋮ A note on real-time one-way alternating multicounter machines ⋮ Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simulation result for the auxiliary pushdown automata
• Complexity of Boolean algebras
• Tree-size bounded alternation
• Space-bounded reducibility among combinatorial problems
• A characterization of the power of vector machines
• Relationships between nondeterministic and deterministic tape complexities
• Provably Difficult Combinatorial Games
• Path Systems: Constructions, Solutions and Applications
• Alternation
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• On Relating Time and Space to Size and Depth
• On the Tape Complexity of Deterministic Context-Free Languages
• The complexity of the membership problem for some extensions of context-free languagest†
• A unified approach to models of synchronous parallel machines
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On context-free languages and push-down automata

This page was built for publication: Tree-size bounded alternation