Alternation
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Note on winning positions on pushdown games with \(\omega\)-regular conditions
- Verifying minimum stable circuit values
- Hardness of equivalence checking for composed finite-state systems
- Optical computing
- On input-revolving deterministic and nondeterministic finite automata
- Theory of one-tape linear-time Turing machines
- Solitaire automata
- Alternating simple multihead finite automata
- Space-bounded hierarchies and probabilistic computations
- Alternating multicounter machines with constant number of reversals
- On the power of alternation in automata theory
- Games against nature
- Speedups of deterministic machines by synchronous parallel machines
- Complete problems in the first-order predicate calculus
- An introduction to parallelism in combinatorial optimization
- Alternating tree automata
- A theory for nondeterminism, parallelism, communication, and concurrency
- On the construction of parallel computers from various basis of Boolean functions
- Alternating on-line Turing machines with only universal states and small space bounds
- Alternation and -type Turing acceptors
- On the complexity of theories of permutations
- Concurrent program schemes and their logics
- Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
- Array processing machines: an abstract model
- Communication in concurrent dynamic logic
- Balance of many-valued transductions and equivalence problems
- Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
- Some observations concerning alternating Turing machines using small space
- Alternating automata on infinite trees
- On nondeterminism in parallel computation
- Finite automata and unary languages
- The problem of space invariance for sequential machines
- On reversal bounded alternating Turing machines
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- The complexity of optimization problems
- Parallel computation with threshold functions
- Decompositions of nondeterministic reductions
- \(\Sigma_ 2SPACE(n)\) is closed under complement
- Relativized alternation and space-bounded computation
- On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
- Some subclasses of context-free languages in NC^ 1
- Subclasses of Presburger arithmetic and the polynomial-time hierarchy
- Dominoes and the complexity of subclasses of logical theories
- The computational complexity of asymptotic problems. I: Partial orders
- Alternating multihead finite automata
- Complexity theory of parallel time and hardware
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Tradeoffs for language recognition on alternating machines
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
- The complexity of reasoning about knowledge and time. I: Lower bounds
- A hierarchy of propositional Horn formuls
- Descriptive characterizations of computational complexity
- A grammatical characterization of alternating pushdown automata
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- Lower bounds for language recognition on two-dimensional alternating multihead machines
- Speeding up inferences using relevance reasoning: a formalism and algorithms
- Unambiguous computations and locally definable acceptance types
- A communication hierarchy of parallel computations
- Three-dimensional alternating Turing machines with only universal states
- On alternation
- Tree-size bounded alternation
- An extension of Savitch's theorem to small space bounds
- On uniform circuit complexity
- On the computational complexity of satisfiability in propositional logics of programs
- The complexity of short two-person games
- Properties that characterize LOGCFL
- On the computational efficiency of symmetric neural networks
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- A note on the space complexity of some decision problems for finite automata
- Iterated stack automata and complexity classes
- Some properties of space-bounded synchronized alternating Turing machines with universal states only
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- The complexity of stochastic games
- Decision problems for propositional linear logic
- A survey of space complexity
- A guide to completeness and complexity for modal logics of knowledge and belief
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Generalizations of Opt P to the polynomial hierarchy
- Alternating automata, the weak monadic theory of trees and its complexity
- Upper bounds on recognition of a hierarchy of non-context-free languages
- On space-bounded synchronized alternating Turing machines
- A characterization of exponential-time languages by alternating context- free grammars
- Intersection and union of regular languages and state complexity
- A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space
- A uniform approach to define complexity classes
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Trade-offs between communication and space
- Complexity of logical theories involving coprimality
- Communication for alternating machines
- Unambiguity of circuits
- Circuit size relative to pseudorandom oracles
- A note on realtime one-way synchronized alternating one-counter automata
- On the complexity of tree embedding problems
- On determining optimal strategies in pursuit games in the plane
- Reflective relational machines
- Properties of probabilistic pushdown automata
- Positive versions of polynomial time
- A note on two-dimensional probabilistic finite automata
- Succinctness as a source of complexity in logical formalisms
This page was built for publication: Alternation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3928246)
