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

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, On 1-inkdot alternating Turing machines with small space, An introduction to parallelism in combinatorial optimization, Alternating tree automata, Simulation of three-dimensional one-marker automata by five-way Turing machines, The complexity of optimizing finite-state transducers, 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 \(\omega\)-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, The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\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, Alternating simple multihead finite automata, A note on three-dimensional alternating Turing machines with space smaller than \(\log m\), Space-bounded hierarchies and probabilistic computations, The Othello game on an \(n\times n\) board is PSPACE-complete, Alternating multicounter machines with constant number of reversals, On the power of alternation in automata theory, The state complexities of some basic operations on regular languages, Nondeterminacy and recursion via stacks and games, Games against nature, Speedups of deterministic machines by synchronous parallel machines, Complete problems in the first-order predicate calculus, Concurrent Dynamic Algebra, The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes, Taming Multirelations, Countdown games, and simulation on (succinct) one-counter nets, Combining Partial Specifications using Alternating Interface Automata, The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Sequent Calculus for Intuitionistic Epistemic Logic IEL, On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions, State-complexity of finite-state devices, state compressibility and incompressibility, ON THE COMPLEXITY OF COALITIONAL REASONING, Multi-Valued Reasoning about Reactive Systems, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, Deciding Parity Games in Quasi-polynomial Time, The Communication Hierarchy of Time and Space Bounded Parallel Machines, Unnamed Item, Unnamed Item, Equations and regular-like expressions for afa, On the power of 1-tape off-line ATMs running in a bounded number of reversals, Unnamed Item, Reversals and alternation, Deciding equivalence of finite tree automata, Locally definable acceptance types for polynomial time machines, Inductive counting below logspace, Empty alternation, The computational complexity of deciding whether a finite algebra generates a minimal variety, Unnamed Item, Complexity limitations on one-turn quantum refereed games, On parallel hierarchies and R ki, Computation models and function algebras, Max Euwe's Set-Theoretic Observations on the Game of Chess — Introductory Notes, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Two-way automata and length-preserving homomorphisms, On balanced versus unbalanced computation trees, Complexity of E0L structural equivalence, Computing on structures, Complexity results for multi-pebble automata and their logics, A note on one-pebble two-dimensional Turing machines, A hierarchy that does not collapse : alternations in low level space, On the complexity of team logic and its two-variable fragment, State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis, Spanning-Tree Games., Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete, Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic, Consensus Game Acceptors and Iterated Transductions, A note on one-pebble two-dimensional Turing machines, The complexity of searching succinctly represented graphs, Minimal Size of Counters for (Real-Time) Multicounter Automata, OWL 2 Profiles: An Introduction to Lightweight Ontology Languages, EXPTIME-complete Decision Problems for Modal and Mixed Specifications, On the complexity of verifying concurrent transition systems, Linear Parsing Expression Grammars, A NOTE ON REBOUND TURING MACHINES, Branching-Time Model-Checking of Probabilistic Pushdown Automata, Alternation for sublogarithmic space-bounded alternating pushdown automata, Unnamed Item, Playing Savitch and Cooking Games, ON ALTERNATING PHRASE-STRUCTURE GRAMMARS, Lower bounds for multiplayer noncooperative games of incomplete information, Unnamed Item, Properties of probabilistic pushdown automata, Unnamed Item, Closest substring problems for regular languages, Converting a Büchi alternating automaton to a usual nondeterministic one, Complement for two-way alternating automata, Hyper-polynomial hierarchies and the polynomial jump, Computing LOGCFL certificates, Unnamed Item, New results concerning synchronized finite automata, Debates with Small Transparent Quantum Verifiers, How Much Lookahead is Needed to Win Infinite Games?, Canonical Models and the Complexity of Modal Team Logic, Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Unnamed Item, How Much Lookahead is Needed to Win Infinite Games?, Unnamed Item, Alternating time versus deterministic time: A separation, Domain mu-calculus, Datalog: Bag Semantics via Set Semantics, CaRet With Forgettable Past, 2-Exp Time lower bounds for propositional dynamic logics with intersection, Unnamed Item, Unnamed Item, Alternating automata: Unifying truth and validity checking for temporal logics, The Complexity of Model-Checking Tail-Recursive Higher-Order Fixpoint Logic, UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n), One-Dimensional Logic over Trees, Universal Disjunctive Concatenation and Star, RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION, Uniform Constraint Satisfaction Problems and Database Theory, Discrete-time control for rectangular hybrid automata, Unnamed Item, Parallel random access machines with powerful instruction sets, (Semi)alternating stack automata, The complexity of online bribery in sequential elections, Alternating and empty alternating auxiliary stack automata., Kleisli, Parikh and Peleg compositions and liftings for multirelations, Quantum alternation, Deterministic versus nondeterministic space in terms of synchronized alternating machines, Parallel pointer machines, A symbolic decision procedure for symbolic alternating finite automata, Hardness vs randomness, Classification of the index sets of low \([n^ p\) and high \([n]^ p\)], Modular strategies for recursive game graphs, Iterated covariant powerset is not a monad, The computational complexity of scenario-based agent verification and design, Speedup of determinism by alternation for multidimensional Turing machines, Complexity results on branching-time pushdown model checking, Deciding unifiability and computing local unifiers in the description logic \(\mathcal{EL}\) without top constructor, Conjunctive grammars and alternating pushdown automata, Alternating weighted automata over commutative semirings, A note on emptiness for alternating finite automata with a one-letter alphabet, Complexity results for two-way and multi-pebble automata and their logics, A remark on middle space bounded alternating Turing machines, The complexity of PDL with interleaving, Computational complexity and constraint logic programming languages, Expressing uniformity via oracles, Separating classes in the exponential-time hierarchy from classes in PH, On the decidability of infix inclusion problem, Null inclusion dependencies in relational databases, Games for active XML revisited, On parallel hierarchies and \(R_k^i\), Common knowledge and update in finite environments, A canonical form of vector machines, On the structural simplicity of machines and languages, Fuzzy alternating Büchi automata over distributive lattices, Model checking interval temporal logics with regular expressions, Entanglement and the complexity of directed graphs, Gap-languages and log-time complexity classes, On the power of alternation on reversal-bounded alternating Turing machines with a restriction, Alternation on cellular automata, Nondeterministic stack register machines, On the parallel complexity of loops, Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\), Typechecking for XML transformers, Decision procedures for inductive Boolean functions based on alternating automata, The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic, From bidirectionality to alternation., Model checking open systems with alternating projection temporal logic, Model checking of pushdown systems for projection temporal logic, P-hardness of the emptiness problem for visibly pushdown languages, Introduction to computability logic, Conjunctive query containment over trees using schema information, Deciding the word problem in pure double Boolean algebras, On the descriptional complexity of stateless deterministic ordered restarting automata, On the complexity of the quantified bit-vector arithmetic with binary encoding, From QBFs to \textsf{MALL} and back via focussing, Fixed point guided abstraction refinement for alternating automata, Discrete-time control for rectangular hybrid automata, Generalized acceptance, succinctness and supernondeterministic finite automata., Reachability relations of timed pushdown automata, A characterization of alternating log time by ramified recurrence, The complexity of synchronizing Markov decision processes, Solving a PSPACE-complete problem with cP systems, Alternating-time temporal logics with linear past, On the efficiency of normal form systems for representing Boolean functions, Transformation from PLTL to automata via NFGs, Weak bisimilarity and regularity of context-free processes is EXPTIME-hard, Finite graph automata for linear and boundary graph languages, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, The complexity of graph languages generated by hyperedge replacement, Alternation in two-way finite automata, Clocked population protocols, Positive announcements, Randomized proofs in arithmetic, P systems attacking hard problems beyond NP: a survey, Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment, A note on two-dimensional probabilistic Turing machines, Domino-tiling games, A nondeterministic Turing machine variant to compute functions, A leaf-time hierarchy of two-dimensional alternating turing machines, Probabilistic game automata, Time-space tradeoffs for satisfiability, The model checking fingerprints of CTL operators, Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Descriptional complexity of regular languages, Query inseparability for \(\mathcal{ALC}\) ontologies, A complexity analysis of bisimilarity for value-passing processes, Symbolic model checking for \(\mu\)-calculus requires exponential time, Alternating finite automata and star-free languages, Efficient implementation of regular languages using reversed alternating finite automata, Width measures of alternating finite automata, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete., Trace semantics via determinization, Alternation and bounded concurrency are reverse equivalent., Pushdown processes: Games and model-checking, How hard is computing the edit distance?, On the complexity of verifying concurrent transition systems, Is your model checker on time? On the complexity of model checking for timed modal logics, Looking at mean-payoff and total-payoff through windows, Uniform strategies, rational relations and jumping automata, Learning residual alternating automata, Synthesis of succinct systems, Decision algorithms for multiplayer noncooperative games of incomplete information, Characterizing parallel time by type 2 recursions with polynomial output length, Taming strategy logic: non-recurrent fragments, Living without Beth and Craig: Definitions and Interpolants in Description and Modal Logics with Nominals and Role Inclusions, On log-time alternating Turing machines of alternation depth k, Subclasses of \textsc{Ptime} interpreted by programming languages, Alternating automatic register machines, Converting finite width AFAs to nondeterministic and universal finite automata, A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings, Probabilism versus Alternation for Automata, Existential and universal width of alternating finite automata, Complexity of exclusive nondeterministic finite automata, On the translation of automata to linear temporal logic, Modal logics and local quantifiers: a zoo in the elementary hierarchy, On some open problems concerning the complexity of cellular arrays, Exponential time analysis of confluent and boundary eNCE graph languages, Bounded tree-width and LOGCFL, Jump complexity of finite automata with translucent letters, Operations on Boolean and Alternating Finite Automata, Unnamed Item, Universal quantifiers and time complexity of random access machines, Turing Machines for Dummies, Edit Distance for Pushdown Automata, On the Complexity of Intersecting Regular, Context-Free, and Tree Languages, SAFE RECURSIVE SET FUNCTIONS, Consensus Game Acceptors, Automata Theory and Model Checking, A Parameterized Halting Problem, The complexity of online manipulation of sequential elections, FO Model Checking on Nested Pushdown Trees, A survey of two-dimensional automata theory, Self-reducibility, Positive relativizations for log space computability, On uniformity within \(NC^ 1\), Shrinking and Expanding Cellular Automata, The Complexity of One-Agent Refinement Modal Logic, Inverse monoids: decidability and complexity of algebraic questions., Propositional dynamic logic with recursive programs, Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition, Constructions for alternating finite automata^∗, LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA, A tableau construction for finite linear-time temporal logic, Computational structure of GPSG models, Restricted Power - Computational Complexity Results for Strategic Defense Games, Expressivity and Complexity of MongoDB Queries, Complexity of Propositional Independence and Inclusion Logic, LoCo—A Logic for Configuration Problems, Nonelementary Complexities for Branching VASS, MELL, and Extensions, Computational Complexity Via Finite Types, Complexity results on register context-free grammars and related formalisms, A computation model with automatic functions and relations as primitive operations, The complexity of searching implicit graphs, SYMBOLIC IMPLEMENTATION OF ALTERNATING AUTOMATA, Complexity of planning for connected agents in a partially known environment, Fixpoint logics over hierarchical structures, Parallelizing time with polynomial circuits, Classifying the computational complexity of problems, Quantitative vs. weighted automata, Recent Advances in Datalog$$^\pm $$, A rewriting framework and logic for activities subject to regulations, A note on the emptiness problem for alternating finite-memory automata, Possibilities of various types of alternating automata, Synthesis of Strategies Using the Hoare Logic of Angelic and Demonic Nondeterminism, Traces of term-automatic graphs, TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE, WIRELESS MOBILE COMPUTING AND ITS LINKS TO DESCRIPTIVE COMPLEXITY, Unnamed Item, Unnamed Item, Emptiness of Multi-pushdown Automata Is 2ETIME-Complete, More Concise Representation of Regular Languages by Automata and Regular Expressions, Run-Time Monitoring of Electronic Contracts, Deterministic Input-Reversal and Input-Revolving Finite Automata, On Alternating Phrase-Structure Grammars, An Infinite Automaton Characterization of Double Exponential Time, Recursion Schemata for NC k, The Complexity of Conjunctive Query Answering in Expressive Description Logics, Yield-languages recognized by alternating tree recognizers, Infinite Runs in Weighted Timed Automata with Energy Constraints, A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines, On some derivation mechanisms and the complexity of their Szilard languages, Visibly rational expressions, In defense of PDDL axioms, Modal and mixed specifications: key decision problems and their complexities, Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata, Modular algorithms for heterogeneous modal logics via multi-sorted coalgebra, Consensual languages and matching finite-state computations, LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata, Isomorphism of Regular Trees and Words, Complexity results for prefix grammars, Analysis of dynamic policies, COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE, The complexity of ranking simple languages, Towards separating nondeterminism from determinism, The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions, Tableaux for constructive concurrent dynamic logic, Alternating automata and temporal logic normal forms, An Automata-Theoretic Approach to Infinite-State Systems, Model checking propositional dynamic logic with all extras, The role of rudimentary relations in complexity theory, Typing in reflective combinatory logic, On complexity of verification of interacting agents' behavior, Factoring and Testing Primes in Small Space, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, PDL with intersection and converse: satisfiability and infinite-state model checking, Coalgebraic Hybrid Logic, Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata, Descriptional and Computational Complexity of Finite Automata, New Results on the Minimum Amount of Useful Space, Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space, Efficient Probabilistically Checkable Debates, Fixpoint Guided Abstraction Refinement for Alternating Automata, On Models of a Nondeterministic Computation, On the Complexity of Szilard Languages of Regulated Grammars, Automatic structures of bounded degree revisited, Alternating Context-Free Languages and Linear Time μ-Calculus with Sequential Composition, Some properties of one-pebble Turing machines with sublogarithmic space, Generation problems, Soft Linear Logic and Polynomial Complexity Classes, Sublogarithmic $\sum _2$-space is not closed under complement and other separation results, Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata