Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership

DOI10.1016/j.tcs.2020.08.023zbMath1498.03113OpenAlexW3080392153MaRDI QIDQ2215960

Pietro Maugeri, Domenico Cantone, Eugenio Giovanni Omodeo

Publication date: 15 December 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.08.023

zbMATH Keywords

NP-completenessexpressibilitysatisfiability problemproof verificationcomputable set theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Axiomatics of classical set theory and its fragments (03E30)

Related Items (2)

Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages ⋮ Complexity Assessments for Decidable Fragments of Set Theory. I: A Taxonomy for the Boolean Case*

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval propagation to reason about sets: Definition and implementation of a practical language
• Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators
• Embedding Boolean expressions into logic programming
• The automation of syllogistic. II: Optimization and complexity issues
• Formative processes with applications to the decision problem in set theory. I: Powerset and singleton operators
• Formative processes with applications to the decision problem in set theory. II. Powerset and singleton operators, finiteness predicate
• Solving quantifier-free first-order constraints over finite sets and binary relations
• A new algorithm for optimal 2-constraint satisfaction and its implications
• {log}: A language for programming in logic with finite sets
• Set unification
• Decision procedures for elementary sublanguages of set theory. I. Multi-level syllogistic and some extensions
• An Introduction to the Technique of Formative Processes in Set Theory
• Computational Logic and Set Theory
• On Sets and Graphs

This page was built for publication: Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership