Paperlane

no. 7 · Tuesday 3 November 2026

Decidability and $\neg$NP-completeness for some languages which extend Boolean Set Theory

Pietro Ursino

math.LO · v2

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
pdf ↗ page arXiv:2108.13913 ↗