Counting quantifiers, successor relations, and logarithmic space
From MaRDI portal
Publication:1362332
DOI10.1006/jcss.1997.1485zbMath0882.68074OpenAlexW1991188222MaRDI QIDQ1362332
Publication date: 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1485
Related Items (26)
Equivalence classes and conditional hardness in massively parallel computations ⋮ Approximate pattern matching and transitive closure logics. ⋮ The complexity of planarity testing ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Unnamed Item ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ Query languages for bags and aggregate functions ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ Solutions and query rewriting in data exchange ⋮ Bounded Treewidth and Space-Efficient Linear Algebra ⋮ Expressive power of SQL. ⋮ The complexity of satisfiability for fragments of hybrid logic. I. ⋮ Program Repair for Hyperproperties ⋮ Game-based notions of locality over finite models ⋮ Pebble Weighted Automata and Weighted Logics ⋮ Unnamed Item ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ First-order logics: some characterizations and closure properties ⋮ Notions of locality and their logical characterizations over finite models ⋮ Planar and grid graph reachability problems ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Verifiable properties of database transactions ⋮ Local properties of query languages ⋮ Lower bounds for invariant queries in logics with counting. ⋮ On the isomorphism problem for decision trees and decision lists
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Reducibility by algebraic projections
- An optimal lower bound on the number of variables for graph identification
- Space-bounded reducibility among combinatorial problems
- Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
- The complexity of iterated multiplication
- Counting quantifiers, successor relations, and logarithmic space
- Logical hierarchies in PTIME
- Tree canonization and transitive closure
- On uniformity within \(NC^ 1\)
- On winning strategies with unary quantifiers
- Parity, circuits, and the polynomial-time hierarchy
- Languages that Capture Complexity Classes
- Problems complete for deterministic logarithmic space
- Space Lower Bounds for Maze Threadability on Restricted Machines
This page was built for publication: Counting quantifiers, successor relations, and logarithmic space
