Complexity Results for First-Order Two-Variable Logic with Counting
From MaRDI portal
computational complexitycountingdecision problemfirst-order logicfirst-order sentencesNEXPTIME-completesatisfiability problem
Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- Two-variable first order logic with counting quantifiers: complexity results
- Complexity of counting first-order logic for the subword order
- Two-variable first-order logic with counting in forests
- Alternating complexity of counting first-order logic for the subword order
- Two-Variable Logic over Countable Linear Orderings
- Complexity of the two-variable fragment with counting quantifiers
- Complexity of two-variable logic on finite trees
- Complexity of two-variable logic on finite trees
- Complexity of two-variable dependence logic and IF-logic
- The complexity of first-order and monadic second-order logic revisited
Cited in
(35)- The guarded fragment with transitive guards
- Satisfiability problem for modal logic with global counting operators coded in binary is \textsc{NExpTime}-complete
- One-variable logic meets Presburger arithmetic
- Data-complexity of the two-variable fragment with counting quantifiers
- A family of dynamic description logics for representing and reasoning about actions
- Two-variable first order logic with counting quantifiers: complexity results
- A tableau decision procedure for \(\mathcal{SHOIQ}\)
- The complexity of finite model reasoning in description logics
- Complexity of the two-variable fragment with counting quantifiers
- Number of variables is equivalent to space
- Enumeration complexity of logical query problems with second-order variables
- Undecidable propositional bimodal logics and one-variable first-order linear temporal logics with counting
- The two-variable fragment with counting and equivalence
- CTL Model-Checking with Graded Quantifiers
- scientific article; zbMATH DE number 408792 (Why is no real title available?)
- On the Decision Problem for Two-Variable First-Order Logic
- Two-Variable Logic over Countable Linear Orderings
- Logics with counting and equivalence
- Decidable first-order modal logics with counting quantifiers
- Counting Objects
- The two-variable fragment with counting revisited
- On the complexity of the Bernays-Schönfinkel class with Datalog
- The ground-negative fragment of first-order logic is -complete
- Weighted first-order model counting in the two-variable fragment with counting quantifiers
- Weighted model counting beyond two-variable logic
- Circuit complexity and the expressive power of generalized first-order formulas
- Regular graphs and the spectra of two-variable logic with counting
- On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics
- Universal first-order logic is superfluous in the second level of the polynomial-time hierarchy
- A description logic based situation calculus
- Two variable logic with ultimately periodic counting
- Two variable logic with ultimately periodic counting
- Fluted logic with counting
- Deciding expressive description logics in the framework of resolution
- A resolution-based decision procedure for \({\mathcal{SHOIQ}}\).
This page was built for publication: Complexity Results for First-Order Two-Variable Logic with Counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943858)
