First-order satisfiability in Gödel logics: an NP-complete fragment

DOI10.1016/J.TCS.2011.07.015zbMATH Open1244.03090OpenAlexW2096504793MaRDI QIDQ650893FDOQ650893

Agata Ciabattoni, Matthias Baaz, Norbert Preining

Publication date: 7 December 2011

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

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

zbMATH Keywords

satisfiabilitymonadic logicexpert system CADIAG-2 for medical diagnosisone-variable fragmentfirst-order Gödel logic

Mathematics Subject Classification ID

Medical applications (general) (92C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Fuzzy logic; logic of vagueness (03B52)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strongly equivalent logic programs
• Metamathematics of fuzzy logic
• Intuitionistic fuzzy logic and intuitionistic fuzzy set theory
• Residuated fuzzy logics with an involutive negation
• T-norm-based logics with an independent involutive negation
• On theories and models in fuzzy predicate logics
• Continuous Fraïssé conjecture
• First-order Gödel logics
• Algebraic Completeness Results for Dummett's LC and Its Extensions
• Monadic Fragments of Gödel Logics: Decidability and Undecidability Results
• On the completenes principle: A study of provability in heyting's arithmetic and extensions
• Embedding logics into product logic
• Linear Kripke frames and Gödel logics
• SAT in Monadic Gödel Logics: A Borderline between Decidability and Undecidability

Cited In (7)

• A PSPACE-complete first-order fragment of computability logic
• Title not available (Why is that?)
• The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard
• Reasoning in fuzzy description logics using automata
• SAT in Monadic Gödel Logics: A Borderline between Decidability and Undecidability
• One-variable fragments of intermediate logics over linear frames
• The ground-negative fragment of first-order logic is -complete

This page was built for publication: First-order satisfiability in Gödel logics: an NP-complete fragment

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