Algebra of Modular Systems: Containment and Equivalence

Authors

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

DOI:

https://doi.org/10.1609/aaai.v35i7.16775

Keywords:

Other Foundations of Knowledge Representation &

Abstract

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.

Downloads

Published

2021-05-18

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

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning