Yoshiki Nakamura - Note on a Translation from First-Order Logic into the Calculus of Relations Preserving Validity and Finite Validity
fi:12365 - Fundamenta Informaticae, December 27, 2025, Volume 195, Issues 1-4: Relational and Algebraic Methods in Computer Science 2024 - https://doi.org/10.46298/fi.12365Note on a Translation from First-Order Logic into the Calculus of Relations Preserving Validity and Finite ValidityArticle
Authors: Yoshiki Nakamura 
In this note, we give a linear-size translation from formulas of first-order logic into equations of the calculus of relations preserving validity and finite validity. Our translation also gives a linear-size conservative reduction from formulas of first-order logic into formulas of the three-variable fragment of first-order logic.
Source: arXiv.org:2310.02845
Volume: Volume 195, Issues 1-4: Relational and Algebraic Methods in Computer Science 2024
Published on: December 27, 2025
Accepted on: June 5, 2024
Submitted on: October 5, 2023
Keywords: Logic in Computer Science