The Exact Complexity of the First-Order Logic Definability Problem
From MaRDI portal
Recommendations
- The complexity of definability by open first-order formulas
- Complexity of the first-order theory of almost all finite structures
- scientific article; zbMATH DE number 1414298
- scientific article; zbMATH DE number 2072508
- The quantifier complexity of polynomial-size iterated definitions in first-order logic
- New Computational Paradigms
- The complexity of first-order and monadic second-order logic revisited
- Generic complexity of first-order theories
Cited in
(16)- Arithmetic complexity of first-order definable subsets of recursive Boolean algebras
- Deciding open definability via subisomorphisms
- Definability, decidability, complexity
- Logical separability of labeled data examples under ontologies
- Deciding quantifier-free definability in finite algebraic structures
- Regularizing conjunctive features for classification
- The limits of decidability for first order logic on CPDA graphs
- The complexity of definability by open first-order formulas
- scientific article; zbMATH DE number 1261672 (Why is no real title available?)
- scientific article; zbMATH DE number 1507188 (Why is no real title available?)
- Completeness for first-order properties on sparse structures with algorithmic applications
- Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
- Completeness for first-order properties on sparse structures with algorithmic applications
- On Existentially First-Order Definable Languages and Their Relation to NP
- Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
- The complexity of deciding quantifier-free definability for unary signatures
This page was built for publication: The Exact Complexity of the First-Order Logic Definability Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5012557)
