3 citations · 3 across the 12 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
math.LO2021
Decidability and NP-completeness for some languages which extend Boolean Set Theory
Pietro Ursino
We prove the decidability for a class of languages which extend BST and NP-completeness for a subclass of them. The languages BST extended with unordered cartesian product, BST ext…
math.LO2021
Decidability of the satisfiability problem for Boolean set theory with the unordered Cartesian product operator
Domenico Cantone, Pietro Ursino
The satisfiability problem for multilevel syllogistic extended with the Cartesian product operator (MLSC) is a long-standing open problem in computable set theory. For long, it was…
math.LO2021
Hilbert's Tenth problem and NP-completeness of Boolean Syllogistic with unordered cartesian product
Domenico Cantone, Pietro Ursino
We relate the decidability problem for BS with unordered cartesian product with Hilbert's Tenth problem and prove that BS with unordered cartesian product is NP-complete.