Deductive program synthesis using logic programming
Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki · 2026-03-20 · 36 (1) · 159-178
DOI: 10.35634/vm260108 ↗At a glance
Journal article in Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, published on 2026-03-20. Written by M. Joudakizadeh and 1 co-authors.
Abstract (original language)
This article presents an approach to deductive program synthesis using Gentzen’s sequent calculus within the framework of logic programming. By leveraging sequent calculus as a formal system for structured logical inference, our method automates the derivation of provably correct programs from specifications expressed in negation-free first-order predicate logic. We formalize the syntax and semantics of sequent calculus, implementing its core inference rules (introduction and elimination rules) as predicates in logic programming to enable scalable synthesis. Practical examples demonstrate the transformation of logical specifications into executable programs. The approach ensures formal correctness through a constructive semantics inspired by Kleene's realizability, with synthesized programs operating in a subrecursive language to guarantee termination. We evaluate the method's strengths, including its reliability for safety-critical systems, and its limitations, such as computational complexity for unbounded constructions. Compared to AI-driven synthesis, our approach prioritizes formal guarantees, complementing modern trends like relational programming. Future research directions include optimizing computational efficiency and extending applicability to complex real-world problems.
Cite
APA
Joudakizadeh, M., & Beltiukov, A. (2026). Deductive program synthesis using logic programming. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 36(1), 159-178. https://doi.org/10.35634/vm260108
Vancouver
Joudakizadeh M, Beltiukov A. Deductive program synthesis using logic programming. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki. 2026;36(1):159-178. doi:10.35634/vm260108
BibTeX
@article{Joudakizadeh2026,
author = {Joudakizadeh, M. and Beltiukov, A.P.},
title = {Deductive program synthesis using logic programming},
journal = {Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki},
year = {2026},
volume = {36},
number = {1},
pages = {159--178},
doi = {10.35634/vm260108}
}
EUVIMED