Algebra of Modular Systems: Containment and Equivalence
Authors: Andrei Bulatov, Eugenia Ternovska6235-6243
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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.Our main technical contribution is a study of the formal problem of Modular System Containment. In this problem, we are given two expressions, and ask whether the structures that satisfy the first one, also satisfy the second one. A crucial related notion is that of homomorphism.Theorem 1 The Modular System Equivalence problem is undecidable in general, even in the finite case.Theorem 2 (Homomorphism Theorem) Let α1 = π(Xi:i J) Φ1(M1,...,Ms) and α2 = π(Xi:i J) Φ2(M1,...,Ms) be two CCMs for J I. Then α1 α2 iff there is a homomorphism ϕ : Aα2 Aα1 such that ϕ(Xi) = Xi for all i J. |
| Researcher Affiliation | Academia | Andrei Bulatov, Eugenia Ternovska Simon Fraser University abulatov@sfu.ca, ter@sfu.ca |
| Pseudocode | No | The paper contains formal definitions, syntax, semantics, and proofs, but no pseudocode or algorithm blocks are provided. |
| Open Source Code | No | The paper is theoretical and does not mention any open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and uses abstract examples for illustration, it does not involve the use or provision of specific datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments or data, therefore there are no training/validation/test dataset splits mentioned. |
| Hardware Specification | No | The paper is theoretical and does not report on specific computational experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and discusses formalisms like ASP and CSP, but it does not list specific software dependencies with version numbers used for its own research or any computational work. |
| Experiment Setup | No | The paper is purely theoretical and does not describe any empirical experiments or their setup, thus no hyperparameter values or training configurations are provided. |