Abstract
This paper introduces and studies the sequential composition and decomposition of propositional logic programs. We show that acyclic programs can be decomposed into single-rule programs and provide a general decomposition result for arbitrary programs. We show that the immediate consequence operator of a program can be represented via composition which allows us to compute its least model without any explicit reference to operators. This bridges the conceptual gap between the syntax and semantics of a propositional logic program in a mathematically satisfactory way.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Data Availability
The manuscript has no data associated.
References
Antić, C.: On cascade products of answer set programs. Theory Pract. Log. Program. 14(4–5), 711–723 (2014)
Antić, C.: Analogical proportions. Ann. Math. Artif. Intell. 90(6), 595–644 (2022). https://doi.org/10.1007/s10472-022-09798-y
Antić, C.: The index and period of a logic program (2023a). https://hal.science/hal-04219244
Antić, C.: Logic program proportions. Annals of Mathematics and Artificial Intelligence (2023b). https://doi.org/10.1007/s10472-023-09904-8
Antić, C.: On syntactically similar logic programs and sequential decompositions (2023c). arXiv:2109.05300pdf
Antić, C.: Sequential composition of answer set programs (2023d). arXiv:2104.12156pdf
Antić, C.: Sequential composition of propositional Krom logic programs (2023e). https://hal.science/hal-04023753
Apt, K.R.: Logic programming. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 493–574. Elsevier, Amsterdam (1990)
Apt, K.R.: From Logic Programming to Prolog. C.A.R. Hoare Series. Prentice Hall, Prentice Hall, Englewood Cliffs, NJ (1997)
Apt, K.R., Bezem, M.: Acyclic programs. N. Gener. Comput. 9(3–4), 335–363 (1991)
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge (2003)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint logic programming–syntax and semantics. ACM Trans. Program. Lang. Syst. 23(1), 1–29 (2001)
Bossi, A., Bugliesi, M., Gabbrielli, M., Levi, G., Meo, M.: Differential logic programs: Programming methodologies and semantics. Sci. Comput. Program. 27, 217–262 (1996)
Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011)
Brogi, A., Lamma, E., Mello, P.: Compositional model-theoretic semantics for logic programs. N. Gener. Comput. 11, 1–21 (1992)
Brogi, A., Mancarella, P., Pedreschi, D., Turini, F.: Meta for modularising logic programming. In: META 1992, pp. 105–119 (1992b)
Brogi, A., Mancarella, P., Pedreschi, D., Turini, F.: Modular logic programming. ACM Trans. Program. Lang. Syst. 16(4), 1361–1398 (1999)
Brogi, A., Turini, F.: Fully abstract compositional semantics for an algebra of logic programs. Theor. Comput. Sci. 149(2), 201–229 (1995)
Bugliesi, M., Lamma, E., Mello, P.: Modularity in logic programming. J. Logic Program. 19–20(1), 443–502 (1994)
Ceri, S., Gottlob, G., Tanca, L.: What you always wanted to know about datalog (and never dared to ask). IEEE Trans. Knowl. Data Eng. 1(1), 146–166 (1989)
Ceri, S., Gottlob, G., Tanca, L.: Logic Programming and Databases. Surveys in Computer Science. Springer-Verlag, Berlin/Heidelberg (1990)
Chen, W., Kifer, M., Warren, D.S.: HiLog: A foundation for higher-order logic programming. J. Logic Program. 15(3), 187–230 (1993)
Clark, K.L.: Negation as failure. In: Gallaire, H., Minker, J. (eds.) Logic and Data Bases, pp. 293–322. Plenum Press, New York (1978)
Coelho, H. Cotta, J.C.: Prolog by Example. How to Learn, Teach, and Use It. Springer-Verlag, Berlin/Heidelberg (1988)
Dao-Tran, M., Eiter, T., Fink, M., Krennwallner, T. Modular.: nonmonotonic logic programming revisited. In: ICLP, LNCS 5649, pp. 145–159. Springer-Verlag, Berlin/Heidelberg (2009)
Dix, J., Osorio, M., Zepeda, C.: A general theory of confluent rewriting systems for logic programming and its applications. Ann. Pure Appl. Logic 108(1–3), 153–188 (2001)
Dong, G., Ginsburg, S.: On the decomposition of datalog program mappings. Theor. Comput. Sci. 76(1), 143–177 (1990)
Dong, G., Ginsburg, S.: On decompositions of chain datalog programs into \(\cal{P} \) (left-)linear 1-rule components. J. Logic Program. 23(3), 203–236 (1995)
Eiter, T., Gottlob, G., Mannila, H.: Disjunctive datalog. ACM Trans. Database Syst. 22(3), 364–418 (1997)
Eiter, T., Ianni, G., Krennwallner, T.: Answer set programming: a primer. In: Reasoning Web. Semantic Technologies for Information Systems, vol. 5689 of Lecture Notes in Computer Science, pp. 40–110. Springer, Heidelberg (2009)
Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the Semantic Web. Artif. Intell. 172(12–13), 1495–1539 (2008)
Eiter, T., Ianni, G., Schindlauer, R., Tompits, H.: A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In: Kaelbling, L.P., Saffiotti, A. (eds.) IJCAI 2005, pp. 90–96 (2005)
Faber, W., Leone, N., Pfeifer, G.: Recursive aggregates in disjunctive logic programs: semantics and complexity. In: Alferes, J., Leite, J. (eds.) JELIA 2004, LNCS 3229, pp. 200–212. Springer, Berlin (2004)
Gaifman, H. Shapiro, E.: Fully abstract institute of mathematics fully abstract compositional semantics for logic programs. In: Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages, pp. 134–142. ACM Press (1989)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. N. Gener. Comput. 9(3–4), 365–385 (1991)
Hill, P., Lloyd, J.W.: The Gödel Programming Language. The MIT Press (1994)
Hodges, W.: Logical features of Horn clauses. In: Gabbay, D.M., Hogger, C.J., Robinson, J.A.(eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 1, pp. 449–503. Clarendon Press, Oxford/New York (1994)
Howie, J.M.: Fundamentals of Semigroup Theory. London Mathematical Society Monographs New Series. Oxford University Press, Oxford (2003)
Ioannidis, Y.E., Wong, E.: Towards an algebraic theory of recursion. J. ACM 38(2), 329–381 (1991)
Kowalski, R.: Logic for Problem Solving. North-Holland, New York (1979)
Krom, M.R.: The decision problem for a class of first-order formulas in which all disjunctions are binary. Math. Logic Q 13(1–2), 15–20 (1967)
Leinster, T.: Higher Operads, Higher Categories, vol. 298 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge (2004)
Lifschitz, V.: Answer Set Programming. Springer Nature Switzerland AG, Cham, Switzerland (2019)
Lloyd, J.W.: Foundations of Logic Programming (2nd edn.). Springer-Verlag, Berlin, Heidelberg (1987)
Maher, M.J.: Equivalences of logic programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, chap. 16, pp. 627–658. Morgan Kaufmann Publishers (1988)
Makowsky, J.A.: Why Horn formulas matter in computer science: Initial structures and generic examples. J. Comput. Syst. Sci. 34(2–3), 266–292 (1987)
Mancarella, P., Pedreschi, D.: An algebra of logic programs. In: Kowalski, R., Bowen, K.A. (eds.) Proceedings of the 5th International Conference on Logic Programming, pp. 1006–1023. The MIT Press, Cambridge MA (1988)
Miller, D., Nadathur, G.: Programming with Higher-Order Logic. Cambridge University Press (2012)
Oikarinen, E.: Modular Answer Set Programming. Ph.D. thesis, Helsinki University of Technology, Helsinki, Finland (2006)
Oikarinen, E., Janhunen, T.: Modular equivalence for normal logic programs. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) Proc. 17th European Conference on Artificial Intelligence, pp. 412–416. IOS Press, Amsterdam, Netherlands (2006)
O’Keefe, R.A.: Towards an algebra for constructing logic programs. In: SLP 1985, pp. 152–160 (1985)
Pelov, N.: Semantics of Logic Programs with Aggregates. Ph.D. thesis, Katholieke Universiteit Leuven, Leuven (2004)
Pereira, F.C.N., Shieber, S.M.: Prolog and Natural-Language Analysis. Microtome Publishing, Brookline, Massachusetts (2002)
Plambeck, T.: Semigroup techniques in recursive query optimization. In: PODS 1990, pp. 145–153 (1990a)
Plambeck, T.E.: Semigroups and Transitive Closure in Deductive Databases. Ph.D. thesis, Stanford University, Stanford (1990b)
Sterling, L., Shapiro, E.: The Art of Prolog: Advanced Programming Techniques (2nd edn.) The MIT Press, Cambridge MA (1994)
van Emden, M.H., Kowalski, R.: The semantics of predicate logic as a programming language. J. ACM 23(4), 733–742 (1976)
Acknowledgements
We would like to thank the reviewers for their thoughtful and constructive comments, and for their helpful suggestions to improve the presentation of the article.
Funding
Open access funding provided by TU Wien (TUW).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Antić, C. Sequential composition of propositional logic programs. Ann Math Artif Intell 92, 505–533 (2024). https://doi.org/10.1007/s10472-024-09925-x
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-024-09925-x