Algebra of Modular Systems: Containment and Equivalence


  • Andrei Bulatov Simon Fraser University
  • Eugenia Ternovska Simon Fraser University


Other Foundations of Knowledge Representation &


The Algebra of Modular System is a KR formalism that allows for combinations of modules written in multiple languages. Informally, a module represents a piece of knowledge. It can be given by a knowledge base, be an agent, an ASP, ILP, CP program, etc. Formally, a module is a class of structures over the same vocabulary. Modules are combined declaratively, using, essentially, operations of Codd's relational algebra. In this paper, we address the problem of checking modular system containment, which we relate to a homomorphism problem. We prove that, for a large class of modular systems, the containment problem (and thus equivalence) is in the complexity class NP, and therefore is solvable by, e.g., SAT solvers. We discuss conditions under which the problem is polynomial time solvable.




How to Cite

Bulatov, A., & Ternovska, E. (2021). Algebra of Modular Systems: Containment and Equivalence. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6235-6243. Retrieved from



AAAI Technical Track on Knowledge Representation and Reasoning