no. 7 · Tuesday 3 November 2026
Decidability and $\neg$NP-completeness for some languages which extend Boolean Set Theory
Abstract
We prove the decidability for a class of languages which extend BST and failure of NP-completeness for a subclass of them. The languages BST extended with unordered cartesian product, BST extended with ordered cartesian product and BST extended with powerset fall in this last subclass.
- comments
- arXiv admin note: substantial text overlap with arXiv:2106.01224
- fields
- Logic