Complexity assessments for decidable fragments of set theory. I: A taxonomy for the Boolean case

DOI10.3233/FI-2021-2050MaRDI QIDQ5158658zbMATH OpenOpenAlexFDO

Authors Domenico Cantone, Andrea de Domenico, Pietro Maugeri, Eugenio Omodeo

Publication date 25 October 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2021-2050

zbMATH Keywords

NP-completenesssatisfiability problemproof verificationexpressibilitycomputable set theoryBoolean set theory

Mathematics Subject Classification ID

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

Recommendations

• Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
• Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators
• Decision procedures for elementary sublanguages of set theory. VI. Multi-level syllogistic extended by the powerset operator
• Techniques of computable set theory with applications to proof verification
• Formative processes with applications to the decision problem in set theory. II. Powerset and singleton operators, finiteness predicate

Cites work

• scientific article; zbMATH DE number 1641581 (Why is no real title available?)
• scientific article; zbMATH DE number 3715506 (Why is no real title available?)
• scientific article; zbMATH DE number 50150 (Why is no real title available?)
• scientific article; zbMATH DE number 3595145 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1354177 (Why is no real title available?)
• scientific article; zbMATH DE number 1140683 (Why is no real title available?)
• scientific article; zbMATH DE number 1507186 (Why is no real title available?)
• scientific article; zbMATH DE number 3068569 (Why is no real title available?)
• A uniform approach to constraint-solving for lists, multisets, compact lists, and sets
• An introduction to the technique of formative processes in set theory
• Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
• Complexity results for classes of quantificational formulas
• Computational logic and set theory. Applying formalized logic to analysis. Foreword by Martin Davis
• Decision procedures for elementary sublanguages of set theory. I. Multi-level syllogistic and some extensions
• Decision procedures for elementary sublanguages of set theory. II. Formulas involving restricted quantifiers, together with ordinal, integer, map, and domain notions
• Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators
• Embedding Boolean expressions into logic programming
• 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
• Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
• On sets and graphs. Perspectives on logic and combinatorics
• Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
• Set unification
• Solving quantifier-free first-order constraints over finite sets and binary relations
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• The automation of syllogistic. II: Optimization and complexity issues
• Which fragments of the interval temporal logic HS are tractable in model checking?
• {log}: A language for programming in logic with finite sets

Cited in

(3)

• On the convexity of a fragment of pure set theory with applications within a Nelson-Oppen framework
• 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. II: A taxonomy for `small' languages involving membership

This page was built for publication: Complexity assessments for decidable fragments of set theory. I: A taxonomy for the Boolean case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158658)