The Exact Complexity of the First-Order Logic Definability Problem

DOI10.1145/2886095zbMath1474.68074OpenAlexW2347545322WikidataQ130863241 ScholiaQ130863241MaRDI QIDQ5012557

Gonzalo Díaz, Marcelo Arenas

Publication date: 25 November 2021

Published in: ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2886095

zbMATH Keywords

first-order logicrelational algebraexpressivenessdefinability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Classical first-order logic (03B10)

Related Items (3)

Regularizing conjunctive features for classification ⋮ Deciding quantifier-free definability in finite algebraic structures ⋮ Logical separability of labeled data examples under ontologies

This page was built for publication: The Exact Complexity of the First-Order Logic Definability Problem