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

DOI10.1016/J.TCS.2011.07.015MaRDI QIDQ650893zbMATH OpenOpenAlexFDO

Authors Matthias Baaz, Agata Ciabattoni, 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)

Recommendations

• SAT in Monadic Gödel Logics: A Borderline between Decidability and Undecidability
• Gödel logics and the fully boxed fragment of FO-LTL
• Monadic Fragments of Gödel Logics: Decidability and Undecidability Results
• First-order Gödel logics
• On the classification of first order Gödel logics

Cites work

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

Cited in

(8)

• A PSPACE-complete first-order fragment of computability logic
• scientific article; zbMATH DE number 1507188 (Why is no real title available?)
• The ^2 fragment of the first-order theory of atomic set constraints is _1⁰-hard
• Reasoning in fuzzy description logics using automata
• Monadic Fragments of Gödel Logics: Decidability and Undecidability Results
• 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)