4 papers · 1 filter
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…
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.
Two Dichotomy Theorems
Domenico Cantone, Pietro Ursino
We introduce the Dichotomy Property, a new property of some languages in Set Computable Theory, in order to explore the expressivity of some languages which are extensions of MLS.…
Comparing the automorphism group of the measure algebra with some groups related to the infinite permutation group of the natural numbers
Pietro Ursino
We prove, by a straight construction, that the automorphism group of the measure algebra and the subgroup of the measure preserving ones cannot be isomorphic to the trivial automor…