Counting quantifiers, successor relations, and logarithmic space

DOI10.1006/jcss.1997.1485zbMath0882.68074OpenAlexW1991188222MaRDI QIDQ1362332

Kousha Etessami

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

zbMATH Keywords

counting quantifierssuccessor relation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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