The undecidability of FO3 and the calculus of relations with just one binary relation

DOI10.1007/978-3-662-58771-3_11MaRDI QIDQ2284182zbMATH OpenOpenAlexFDO

Authors Yoshiki Nakamura

Publication date 14 January 2020

Full work available at URL https://doi.org/10.1007/978-3-662-58771-3_11

zbMATH Keywords

first-order logicthe calculus of relationsundecidability

Mathematics Subject Classification ID

General logic (03Bxx) Logic in artificial intelligence (68T27)

Recommendations

• Small substructures and decidability issues for first-order logic with two variables
• scientific article; zbMATH DE number 887303
• Undecidability results on two-variable logics
• Undecidability of representability as binary relations

Cited in

(6)

• Expressive power and succinctness of the positive calculus of binary relations
• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• Expressive Power and Succinctness of the Positive Calculus of Relations
• Derivatives on graphs for the positive calculus of relations with transitive closure
• Note on a translation from first-order logic into the calculus of relations preserving validity and finite validity
• Undecidability of the positive calculus of relations with transitive closure and difference: hypothesis elimination using graph loops

This page was built for publication: The undecidability of FO3 and the calculus of relations with just one binary relation

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