Alternation

DOI10.1145/322234.322243zbMath0473.68043OpenAlexW4241108585WikidataQ55878075 ScholiaQ55878075MaRDI QIDQ3928246

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322234.322243

zbMATH Keywords

nondeterminismalternating pushdown automataalternating Turing machinescomplexity classes of languagesalternating finite-state automatasubrecursive quantifier hierarchies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items (only showing first 100 items - show all)

Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits ⋮ Bounded situation calculus action theories ⋮ A note on alternating one-pebble Turing machines with sublogarithmic space ⋮ State explosion in almost-sure probabilistic reachability ⋮ On the complexity of the two-variable guarded fragment with transitive guards ⋮ Hypersequent rules with restricted contexts for propositional modal logics ⋮ Deciding Boolean algebra with Presburger arithmetic ⋮ Towards more expressive ontology languages: the query answering problem ⋮ Computational inductive definability ⋮ Weighted hypertree decompositions and optimal query plans ⋮ A survey of timed automata for the development of real-time systems ⋮ Branching-time model-checking of probabilistic pushdown automata ⋮ Information tracking in games on graphs ⋮ Model-checking hierarchical structures ⋮ Computation as an unbounded process ⋮ Complexity of equations over sets of natural numbers ⋮ Coalgebraic semantics of modal logics: an overview ⋮ On attribute grammars without attribute synthesis ⋮ An alternating hierarchy for finite automata ⋮ The dag-width of directed graphs ⋮ A dynamic deontic logic for complex contracts ⋮ Hypothetical datalog: Complexity and expressibility ⋮ Satisfiability of formulae with one \(\forall\) is decidable in exponential time ⋮ On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals ⋮ One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ Polynomial size \(\Omega\)-branching programs and their computational power ⋮ 0-1 laws and decision problems for fragments of second-order logic ⋮ On the computational complexity of behavioral description-based web service composition ⋮ Hardness of preorder checking for basic formalisms ⋮ An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic ⋮ Two-way automata making choices only at the endmarkers ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Deductive verification of alternating systems ⋮ The complexity of debate checking ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ On input read-modes of alternating Turing machines ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ The complexity of pursuit on a graph ⋮ Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines ⋮ Proof synthesis and reflection for linear arithmetic ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ The complexity of querying indefinite data about linearly ordered domains ⋮ Reusing and modifying rulebases by predicate substitution ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ A finite set of functions with an EXPTIME-complete composition problem ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ Interactive proof systems and alternating time-space complexity ⋮ Arithmetization: A new method in structural complexity theory ⋮ Continuous alternation: the complexity of pursuit in continuous domains ⋮ Partial orders on words, minimal elements of regular languages, and state complexity ⋮ If not empty, NP-P is topologically large ⋮ On the complexity of queries in the logical data model ⋮ Recursively indefinite databases ⋮ The complexity of controlling candidate-sequential elections ⋮ More concise representation of regular languages by automata and regular expressions ⋮ Hypertree decompositions and tractable queries ⋮ Pushdown module checking ⋮ Quasi-interpretations. A way to control resources ⋮ Conformant plans and beyond: principles and complexity ⋮ A logic for reasoning about counterfactual emotions ⋮ Alternating states for dual nondeterminism in imperative programming ⋮ Logical aspects of Cayley-graphs: the group case ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Reachability on prefix-recognizable graphs ⋮ Group announcement logic ⋮ On state-alternating context-free grammars ⋮ Automata on infinite objects and their applications to logic and programming ⋮ The strong exponential hierarchy collapses ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ Note on winning positions on pushdown games with \(\omega\)-regular conditions ⋮ Verifying minimum stable circuit values ⋮ The complexity of one-agent refinement modal logic ⋮ Hardness of equivalence checking for composed finite-state systems ⋮ Constructive modal logics. I ⋮ Turing machines with access to history ⋮ Some classes of languages in \(NC^ 1\) ⋮ Prediction-preserving reducibility ⋮ Optical computing ⋮ On input-revolving deterministic and nondeterministic finite automata ⋮ Theory of one-tape linear-time Turing machines ⋮ Fuzzy alternating automata over distributive lattices ⋮ A note on alternating on-line Turing machines ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories ⋮ Two-dimensional alternative Turing machines ⋮ Alternating finite automata on \(\omega\)-words ⋮ Solitaire automata ⋮ The complexity of two-player games of incomplete information ⋮ The complexity of the satisfiability problem for Krom formulas ⋮ Results on the propositional \(\mu\)-calculus ⋮ Global and local views of state fairness ⋮ Pseudorandom bits for constant depth circuits ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes ⋮ A note on real-time one-way alternating multicounter machines ⋮ On the power of synchronization in parallel computations ⋮ Collecting statistics over runtime executions ⋮ Computation of equilibria in noncooperative games

This page was built for publication: Alternation