×

SAT in monadic Gödel logics: a borderline between decidability and undecidability. (English) Zbl 1246.03046

Ono, Hiroakira (ed.) et al., Logic, language, information and computation. 16th international workshop, WoLLIC 2009, Tokyo, Japan, June 21–24, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02260-9/pbk). Lecture Notes in Computer Science 5514. Lecture Notes in Artificial Intelligence, 113-123 (2009).
Summary: We investigate satisfiability in the monadic fragment of first-order Gödel logics. These are a family of finite- and infinite-valued logics where the sets of truth values \(V\) are closed subsets of \([0, 1]\) containing 0 and 1. We identify conditions on the topological type of \(V\) that determine the decidability or undecidability of their satisfiability problem.
For the entire collection see [Zbl 1165.03002].

MSC:

03B52 Fuzzy logic; logic of vagueness
03B25 Decidability of theories and sets of sentences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baaz, M.: Infinite-valued Gödel logics with 0-1-projections and relativizations. In: Proceedings Gödel 1996. Kurt Gödel’s Legacy. LNL, vol. 6, pp. 23–33. Springer, Heidelberg (1996) · Zbl 0862.03015
[2] Baaz, M., Ciabattoni, A., Fermüller, C.G.: Herbrand’s Theorem for Prenex Gödel Logic and its Consequences for Theorem Proving. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS, vol. 2250, pp. 201–216. Springer, Heidelberg (2001) · Zbl 1275.03098 · doi:10.1007/3-540-45653-8_14
[3] Baaz, M., Ciabattoni, A., Fermüller, C.G.: Monadic Fragments of Gödel Logics: Decidability and Undecidability Results. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS (LNAI), vol. 4790, pp. 77–91. Springer, Heidelberg (2007) · Zbl 1138.03025 · doi:10.1007/978-3-540-75560-9_8
[4] Baaz, M., Preining, N., Zach, R.: First-order Gödel logics. Annals of Pure and Applied Logic 147, 23–47 (2007) · Zbl 1146.03010 · doi:10.1016/j.apal.2007.03.001
[5] Baaz, M., Hájek, P., Svejda, D., Krajícek, J.: Embedding Logics into Product Logic. Studia Logica 61(1), 35–47 (1998) · Zbl 0962.03019 · doi:10.1023/A:1005026229560
[6] Beckmann, A., Goldstern, M., Preining, N.: Continuous Fraïssé conjecture. Order 25(4), 281–298 (2008) · Zbl 1171.03027 · doi:10.1007/s11083-008-9094-4
[7] Gabbay, D.M.: Decidability of some intuitionistic predicate theories. J. of Symbolic Logic 37, 579–587 (1972) · Zbl 0266.02025 · doi:10.2307/2272747
[8] Hájek, P.: Metamathematics of Fuzzy Logic. Kluwer, Dordrecht (1998) · Zbl 0937.03030 · doi:10.1007/978-94-011-5300-3
[9] Hájek, P.: Arithmetical complexity of fuzzy predicate logics: a survey II. Annals of Pure and Applied Logic (to appear) · Zbl 1182.03050 · doi:10.1016/j.apal.2009.05.015
[10] Hájek, P.: Monadic Fuzzy Predicate Logics. Studia Logica 71(2), 165–175 (2002) · Zbl 1006.03023 · doi:10.1023/A:1016544704961
[11] Hájek, P., Cintula, P.: On theories and models in fuzzy predicate logics. Journal of Symbolic Logic 71(3), 863–880 (2006) · Zbl 1111.03030 · doi:10.2178/jsl/1154698581
[12] Kechris, A.S.: Classical Descriptive Set Theory. Springer, Heidelberg (1995) · Zbl 0819.04002 · doi:10.1007/978-1-4612-4190-4
[13] Preining, N.: Complete Recursive Axiomatizability of Gödel Logics. PhD thesis, Vienna University of Technology, Austria (2003)
[14] Ragaz, M.: Die Unentscheidbarkeit der einstelligen unendlichwertigen Prädikatenlogik. Arch. math. Logik 23, 129–139 (1983) · Zbl 0533.03007 · doi:10.1007/BF02023019
[15] Rogers, H.: Certain logical reduction and decision problems. Annals of Mathematics 64, 264–284 (1956) · Zbl 0074.01403 · doi:10.2307/1969974
[16] Takeuti, G., Titani, T.: Intuitionistic fuzzy logic and intuitionistic fuzzy set theory. J. of Symbolic Logic 49, 851–866 (1984) · Zbl 0575.03015 · doi:10.2307/2274139
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.