Counting quantifiers, successor relations, and logarithmic space
From MaRDI portal
(Redirected from Publication:1362332)
Recommendations
Cites work
- scientific article; zbMATH DE number 3115890 (Why is no real title available?)
- scientific article; zbMATH DE number 17544 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 1306869 (Why is no real title available?)
- scientific article; zbMATH DE number 512825 (Why is no real title available?)
- scientific article; zbMATH DE number 618821 (Why is no real title available?)
- scientific article; zbMATH DE number 1414308 (Why is no real title available?)
- 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
- Counting quantifiers, successor relations, and logarithmic space
- Languages that Capture Complexity Classes
- Logical hierarchies in PTIME
- On uniformity within \(NC^ 1\)
- On winning strategies with unary quantifiers
- Parity, circuits, and the polynomial-time hierarchy
- Problems complete for deterministic logarithmic space
- Reducibility by algebraic projections
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Space-bounded reducibility among combinatorial problems
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The complexity of iterated multiplication
- Tree canonization and transitive closure
- Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(30)- Lower bounds for invariant queries in logics with counting.
- Planar and grid graph reachability problems
- The complexity of satisfiability for fragments of hybrid logic. I.
- Program Repair for Hyperproperties
- scientific article; zbMATH DE number 6970796 (Why is no real title available?)
- Expressive power of SQL.
- Pebble weighted automata and weighted logics
- 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
- The isomorphism problem for \(k\)-trees is complete for logspace
- On the isomorphism problem for decision trees and decision lists
- Verifiable properties of database transactions
- Query languages for bags and aggregate functions
- Descriptive complexity for counting complexity classes
- Notions of locality and their logical characterizations over finite models
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- A logical characterization of the counting hierarchy
- scientific article; zbMATH DE number 935103 (Why is no real title available?)
- 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 ( y P) quantifier
- First-order logics: some characterizations and closure properties
- Compressed Decision Problems in Hyperbolic Groups.
- Exclusion problems and the cardinality of logical space
- Bounded treewidth and space-efficient linear algebra
- 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)
