Algebra of Modular Systems: Containment and Equivalence
Keywords:Other Foundations of Knowledge Representation &
AbstractThe 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. https://doi.org/10.1609/aaai.v35i7.16775
AAAI Technical Track on Knowledge Representation and Reasoning