Navegar

Colección

Datos Estadísticas

Artículo

Caicedo, X.; Metcalfe, G.; Rodríguez, R.; Rogger, J. "Decidability of order-based modal logics" (2017) Journal of Computer and System Sciences. 88:53-74
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Decidability of the validity problem is established for a family of many-valued modal logics, notably Gödel modal logics, where propositional connectives are evaluated according to the order of values in a complete sublattice of the real unit interval [0,1], and box and diamond modalities are evaluated as infima and suprema over (many-valued) Kripke frames. If the sublattice is infinite and the language is sufficiently expressive, then the standard semantics for such a logic lacks the finite model property. It is shown here, however, that, given certain regularity conditions, the finite model property holds for a new semantics for the logic, providing a basis for establishing decidability and PSPACE-completeness. Similar results are also established for S5 logics that coincide with one-variable fragments of first-order many-valued logics. In particular, a first proof is given of the decidability and co-NP-completeness of validity in the one-variable fragment of first-order Gödel logic. © 2017 Elsevier Inc.

Registro:

Documento: Artículo
Título:Decidability of order-based modal logics
Autor:Caicedo, X.; Metcalfe, G.; Rodríguez, R.; Rogger, J.
Filiación:Departamento de Matemáticas, Universidad de los Andes, Bogotá, Colombia
Mathematical Institute, University of Bern, Switzerland
Departamento de Computación, Universidad de Buenos Aires, Argentina
Palabras clave:Complexity; Decidability; Finite model property; Gödel logics; Many-valued logics; Modal logics; One-variable fragments; Computability and decidability; Computer circuits; Formal logic; Semantics; Complexity; Finite model property; Modal logic; Np-completeness; Pspace completeness; Regularity condition; Unit intervals; Variable fragment; Many valued logics
Año:2017
Volumen:88
Página de inicio:53
Página de fin:74
DOI: http://dx.doi.org/10.1016/j.jcss.2017.03.012
Título revista:Journal of Computer and System Sciences
Título revista abreviado:J. Comput. Syst. Sci.
ISSN:00220000
CODEN:JCSSB
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v88_n_p53_Caicedo

Referencias:

  • Baaz, M., Preining, N., Zach, R., First-order Gödel logics (2007) Ann. Pure Appl. Log., 147, pp. 23-47
  • Beckmann, A., Goldstern, M., Preining, N., Continuous Fraïssé conjecture (2008) Order, 25 (4), pp. 281-298
  • Bezhanishvili, G., Zakharyaschev, M., Logics over MIPC (1997) Proceedings of Sequent Calculus and Kripke Semantics for Non-Classical Logics, RIMS Kokyuroku 1021, Kyoto University, pp. 86-95
  • Blackburn, P., de Rijke, M., Venema, Y., Modal Logic (2001), Cambridge University Press; Bobillo, F., Delgado, M., Gómez-Romero, J., Straccia, U., Fuzzy description logics under Gödel semantics (2009) Int. J. Approx. Reason., 50 (3), pp. 494-514
  • Bou, F., Esteva, F., Godo, L., Rodríguez, R., On the minimum many-valued logic over a finite residuated lattice (2011) J. Log. Comput., 21 (5), pp. 739-790
  • Bull, R.A., MIPC as formalisation of an intuitionist concept of modality (1966) J. Symb. Log., 31, pp. 609-616
  • Caicedo, X., Metcalfe, G., Rodríguez, R., Rogger, J., A finite model property for Gödel modal logics (2013) Proceedings of WoLLIC 2013, LNCS, 8701, pp. 226-237. , Springer
  • Caicedo, X., Rodríguez, R., Standard Gödel modal logics (2010) Stud. Log., 94 (2), pp. 189-214
  • Caicedo, X., Rodríguez, R., Bi-modal Gödel logic over [0,1]-valued Kripke frames (2015) J. Log. Comput., 25 (1), pp. 37-55
  • Ciabattoni, A., Metcalfe, G., Montagna, F., Algebraic and proof-theoretic characterizations of truth stressers for MTL and its extensions (2010) Fuzzy Sets Syst., 161, pp. 369-389
  • Diaconescu, D., Georgescu, G., Tense operators on MV-algebras and Łukasiewicz–Moisil algebras (2007) Fundam. Inform., 81 (4), pp. 379-408
  • Diaconescu, D., Metcalfe, G., Schnüriger, L., Axiomatizing a real-valued modal logic (2016) Proceedings of AiML 2016, pp. 236-251. , King's College Publications
  • Dummett, M., A propositional calculus with denumerable matrix (1959) J. Symb. Log., 24, pp. 97-106
  • Fitting, M.C., Many-valued modal logics (1991) Fundam. Inform., 15, pp. 235-254
  • Fitting, M.C., Many-valued modal logics II (1992) Fundam. Inform., 17, pp. 55-73
  • Godo, L., Hájek, P., Esteva, F., A fuzzy modal logic for belief functions (2003) Fundam. Inform., 57 (2-4), pp. 127-146
  • Godo, L., Rodríguez, R., A fuzzy modal logic for similarity reasoning (1999) Fuzzy Logic and Soft Computing, pp. 33-48. , Kluwer
  • Hájek, P., Metamathematics of Fuzzy Logic (1998), Kluwer Dordrecht; Hájek, P., On very true (2001) Fuzzy Sets Syst., 124, pp. 329-334
  • Hájek, P., Making fuzzy description logic more general (2005) Fuzzy Sets Syst., 154 (1), pp. 1-15
  • Hájek, P., Harmancová, D., Esteva, F., Garcia, P., Godo, L., On modal logics for qualitative possibility in a fuzzy setting (1994) Proceedings of UAI 1994, pp. 278-285
  • Hansoul, G., Teheux, B., Extending Łukasiewicz logics with a modality: algebraic approach to relational semantics (2013) Stud. Log., 101 (3), pp. 505-545
  • Kontchakov, R., Kurucz, A., Zakharyaschev, M., Undecidability of first-order intuitionistic and modal logics with two variables (2005) Bull. Symb. Log., 11 (3), pp. 428-438
  • Ladner, R.E., The computational complexity of provability in systems of modal propositional logic (1977) SIAM J. Comput., 6 (3), pp. 467-480
  • Marx, M., Complexity of Intuitionistic Predicate Logic with One Variable (2001), Technical Report PP-2001-01 ILLC Scientific Publications Amsterdam; Metcalfe, G., Olivetti, N., Towards a proof theory of Gödel modal logics (2011) Log. Methods Comput. Sci., 7 (2), pp. 1-27
  • Metcalfe, G., Olivetti, N., Gabbay, D., Proof Theory for Fuzzy Logics (2008) Applied Logic, 36. , Springer
  • Mortimer, M., On languages with two variables (1975) Z. Math. Log. Grundl. Math., 21, pp. 135-140
  • Priest, G., Many-valued modal logics: a simple approach (2008) Rev. Symb. Log., 1, pp. 190-203
  • Prior, A., Time and Modality (1957), Clarendon Press Oxford; Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities (1970) J. Comput. Syst. Sci., 4 (2), pp. 177-192
  • Schockaert, S., De Cock, M., Kerre, E., Spatial reasoning in a fuzzy region connection calculus (2009) Artif. Intell., 173 (2), pp. 258-298
  • Servi, G.F., Axiomatizations for some intuitionistic modal logics (1984) Rend. Semin. Mat. Univ. Politec. Torino, 42, pp. 179-194
  • Straccia, U., Reasoning within fuzzy description logics (2001) J. Artif. Intell. Res., 14, pp. 137-166
  • Wolter, F., Superintuitionistic companions of classical modal logics (1997) Stud. Log., 58 (2), pp. 229-259

Citas:

---------- APA ----------
Caicedo, X., Metcalfe, G., Rodríguez, R. & Rogger, J. (2017) . Decidability of order-based modal logics. Journal of Computer and System Sciences, 88, 53-74.
http://dx.doi.org/10.1016/j.jcss.2017.03.012
---------- CHICAGO ----------
Caicedo, X., Metcalfe, G., Rodríguez, R., Rogger, J. "Decidability of order-based modal logics" . Journal of Computer and System Sciences 88 (2017) : 53-74.
http://dx.doi.org/10.1016/j.jcss.2017.03.012
---------- MLA ----------
Caicedo, X., Metcalfe, G., Rodríguez, R., Rogger, J. "Decidability of order-based modal logics" . Journal of Computer and System Sciences, vol. 88, 2017, pp. 53-74.
http://dx.doi.org/10.1016/j.jcss.2017.03.012
---------- VANCOUVER ----------
Caicedo, X., Metcalfe, G., Rodríguez, R., Rogger, J. Decidability of order-based modal logics. J. Comput. Syst. Sci. 2017;88:53-74.
http://dx.doi.org/10.1016/j.jcss.2017.03.012