Number of quantifiers is better than number of tape cells

DOI10.1016/0022-0000(81)90039-8zbMath0486.03019OpenAlexW2043507528MaRDI QIDQ1164622

Publication date: 1981

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

Full work available at URL: https://hdl.handle.net/1813/6250

zbMATH Keywords

lower bounds Turing machine complexity measure quantifier rank Ehrenfeucht- Fraisse games quantifier number uniform sequence of first order formulas

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items (54)

Universal quantifiers and time complexity of random access machines ⋮ Hyperplane separation technique for multidimensional mean-payoff games ⋮ On the universal and existential fragments of the \(\mu\)-calculus ⋮ Specification and Verification of Multi-Agent Systems ⋮ Graph Games and Reactive Synthesis ⋮ A Dynamic Algorithm for Reachability Games Played on Trees ⋮ Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition ⋮ Isomorphisms and 1-L reductions ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Dyn-FO: A parallel, dynamic complexity class ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Descriptive characterizations of computational complexity ⋮ Model-checking iterated games ⋮ The dimension of the negation of transitive closure ⋮ Bounds for the Quantifier Depth in Finite-Variable Logics ⋮ Reasoning About Substructures and Games ⋮ A survey of stochastic \(\omega \)-regular games ⋮ Optimal controller synthesis for timed systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ First-order spectra with one variable ⋮ Reasoning about graded strategy quantifiers ⋮ Unnamed Item ⋮ Discrete-time control for rectangular hybrid automata ⋮ Optimal Reachability in Divergent Weighted Timed Games ⋮ Upper and lower bounds for first order expressibility ⋮ Two-way automata making choices only at the endmarkers ⋮ Stochastic limit-average games are in EXPTIME ⋮ The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems ⋮ Concurrent reachability games ⋮ On the Unusual Effectiveness of Logic in Computer Science ⋮ Algorithms and conditional lower bounds for planning problems ⋮ Capturing complexity classes by fragments of second-order logic ⋮ Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives ⋮ A survey of partial-observation stochastic parity games ⋮ Finite-model theory -- A personal perspective ⋮ Quantitative fair simulation games ⋮ Doomsday equilibria for omega-regular games ⋮ An optimal lower bound on the number of variables for graph identification ⋮ Inherent complexity of recursive queries ⋮ Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives ⋮ Pruning external minimality checking for answer set programs using semantic dependencies ⋮ CEGAR for compositional analysis of qualitative properties in Markov decision processes ⋮ Unnamed Item ⋮ The model checking fingerprints of CTL operators ⋮ Unnamed Item ⋮ Discrete-time control for rectangular hybrid automata ⋮ On the definability of properties of finite graphs ⋮ Complexity of weak acceptance conditions in tree automata. ⋮ Unnamed Item ⋮ Expand, enlarge and check: new algorithms for the coverability problem of WSTS ⋮ Good-for-Game QPTL: An Alternating Hodges Semantics ⋮ Logical and schematic characterization of complexity classes

Cites Work

This page was built for publication: Number of quantifiers is better than number of tape cells