Counting quantifiers, successor relations, and logarithmic space

DOI10.1006/JCSS.1997.1485zbMATH Open0882.68074OpenAlexW1991188222MaRDI QIDQ1362332FDOQ1362332

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

Recommendations

• Lower bounds for invariant queries in logics with counting.
• Relativized logspace and generalized quantifiers over finite ordered structures
• scientific article; zbMATH DE number 1136077
• On the expressive power of counting

zbMATH Keywords

counting quantifierssuccessor relation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On uniformity within \(NC^ 1\)
• Problems complete for deterministic logarithmic space
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Title not available (Why is that?)
• Parity, circuits, and the polynomial-time hierarchy
• Languages that Capture Complexity Classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• An optimal lower bound on the number of variables for graph identification
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting quantifiers, successor relations, and logarithmic space
• On winning strategies with unary quantifiers
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Space-bounded reducibility among combinatorial problems
• Reducibility by algebraic projections
• The complexity of iterated multiplication
• Logical hierarchies in PTIME
• Title not available (Why is that?)
• Tree canonization and transitive closure
• Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (30)

• Lower bounds for invariant queries in logics with counting.
• Planar and grid graph reachability problems
• Program Repair for Hyperproperties
• Title not available (Why is that?)
• The complexity of satisfiability for fragments of hybrid logic. I.
• Bounded Treewidth and Space-Efficient Linear Algebra
• Expressive power of SQL.
• Local properties of query languages
• Approximate pattern matching and transitive closure logics.
• Counting quantifiers, successor relations, and logarithmic space
• Equivalence classes and conditional hardness in massively parallel computations
• On the isomorphism problem for decision trees and decision lists
• The isomorphism problem for \(k\)-trees is complete for logspace
• Notions of locality and their logical characterizations over finite models
• Verifiable properties of database transactions
• Query languages for bags and aggregate functions
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• A logical characterization of the counting hierarchy
• Title not available (Why is that?)
• Game-based notions of locality over finite models
• The complexity of planarity testing
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• On lovely pairs and the \((\exists y\in P)\) quantifier
• First-order logics: some characterizations and closure properties
• Pebble Weighted Automata and Weighted Logics
• Compressed Decision Problems in Hyperbolic Groups.
• Exclusion problems and the cardinality of logical space
• Title not available (Why is that?)
• Log-space algorithms for paths and matchings in \(k\)-trees
• Solutions and query rewriting in data exchange

This page was built for publication: Counting quantifiers, successor relations, and logarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362332)