Alternation
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Prediction-preserving reducibility
- Complexity results for multi-pebble automata and their logics
- CaRet with forgettable past
- A survey of timed automata for the development of real-time systems
- Branching-time model-checking of probabilistic pushdown automata
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- A note on alternating on-line Turing machines
- Two-dimensional alternative Turing machines
- On quantified propositional logics and the exponential time hierarchy
- A canonical form of vector machines
- Information tracking in games on graphs
- Universal quantifiers and time complexity of random access machines
- From QBFs to \textsf{MALL} and back via focussing
- A space lower bound for acceptance by one-way _2-alternating machines
- State-complexity of finite-state devices, state compressibility and incompressibility
- Tradeoffs for language recognition on alternating machines
- Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
- Logical aspects of Cayley-graphs: the group case
- Converting finite width AFAs to nondeterministic and universal finite automata
- Alternation and -type Turing acceptors
- On the complexity of theories of permutations
- On complexity of verification of interacting agents' behavior
- Traces of term-automatic graphs
- Branching-time model-checking of probabilistic pushdown automata
- Polynomial size \(\Omega\)-branching programs and their computational power
- scientific article; zbMATH DE number 7455737 (Why is no real title available?)
- Constructions for alternating finite automata∗
- Playing Savitch and cooking games
- Query inseparability for \(\mathcal{ALC}\) ontologies
- Symmetric synthesis
- A note on the emptiness problem for alternating finite-memory automata
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Continuous alternation: the complexity of pursuit in continuous domains
- Run-Time Monitoring of Electronic Contracts
- Complexity results for prefix grammars
- scientific article; zbMATH DE number 7104930 (Why is no real title available?)
- Modal and mixed specifications: key decision problems and their complexities
- Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata
- On the complexity of the quantified bit-vector arithmetic with binary encoding
- Uniform strategies, rational relations and jumping automata
- The complexity of pursuit on a graph
- Alternating automata: unifying truth and validity checking for temporal logics
- LoCo—A Logic for Configuration Problems
- A rewriting framework and logic for activities subject to regulations
- Learning residual alternating automata
- Alternation on cellular automata
- Nondeterministic stack register machines
- Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\)
- The complexity of ranking simple languages
- Deciding Parity Games in Quasi-polynomial Time
- Arithmetization: A new method in structural complexity theory
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- The complexity of the satisfiability problem for Krom formulas
- Iterated covariant powerset is not a monad
- Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
- Automata theory and model checking
- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
- Model checking of pushdown systems for projection temporal logic
- On the efficiency of normal form systems for representing Boolean functions
- On the complexity of \(\mathsf{ATL}\) and \(\mathsf{ATL}^*\) module checking
- The computational complexity of scenario-based agent verification and design
- A tableau construction for finite linear-time temporal logic
- SYMBOLIC IMPLEMENTATION OF ALTERNATING AUTOMATA
- A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings
- Concurrent program schemes and their logics
- Datalog: Bag Semantics via Set Semantics
- On the complexity of Szilard languages of regulated grammars
- Bounded fixed-point definability and tabular recognition of languages
- Relations among parallel and sequential computation models
- The dag-width of directed graphs
- Efficient normalization of linear temporal logic
- Decision procedures for inductive Boolean functions based on alternating automata
- From bidirectionality to alternation.
- Constraint automata on infinite data trees: from CTL\((\mathbb{Z})\text{CTL}^*(\mathbb{Z})\) to decision procedures
- Symbolic model checking for -calculus requires exponential time
- P systems attacking hard problems beyond NP: a survey
- Kleisli, Parikh and Peleg compositions and liftings for multirelations
- Shrinking and expanding cellular automata
- Deterministic sub-exponential algorithm for discounted-sum games with unary weights
- Nondeterminacy and recursion via stacks and games
- Circuit complexity before the dawn of the new millennium
- Complete problems in the first-order predicate calculus
- Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
- Deciding equivalence of finite tree automata
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction
- Properties of probabilistic pushdown automata
- Locally definable acceptance types for polynomial time machines
- Alternating and empty alternating auxiliary stack automata.
- On the power of automata minimization in reactive synthesis
- The Complexity of Conjunctive Query Answering in Expressive Description Logics
- Maximal universal width of an AFA is NP-hard
- How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
- Synthesis of data word transducers
- The problem of space invariance for sequential machines
- scientific article; zbMATH DE number 7577569 (Why is no real title available?)
- Decompositions of nondeterministic reductions
- scientific article; zbMATH DE number 79114 (Why is no real title available?)
- The complexity of synchronizing Markov decision processes
- Model-checking hierarchical structures
- Some subclasses of context-free languages in NC^ 1
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)
