Artículo
Areces, C.; Figueira, D.; Figueira, S.; Mera, S. "Expressive power and decidability for memory logics" (2008) 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008. 5110 LNAI:56-68
Consulte la política de Acceso Abierto del editor
Abstract:
Taking as inspiration the hybrid logic , we introduce a new family of logics that we call memory logics. In this article we present in detail two interesting members of this family defining their formal syntax and semantics. We then introduce a proper notion of bisimulation and investigate their expressive power (in comparison with modal and hybrid logics). We will prove that in terms of expressive power, the memory logics we discuss in this paper are more expressive than orthodox modal logic, but less expressive than . We also establish the undecidability of their satisfiability problems. © 2008 Springer-Verlag Berlin Heidelberg.
Registro:
| Documento: | Artículo |
| Título: | Expressive power and decidability for memory logics |
| Autor: | Areces, C.; Figueira, D.; Figueira, S.; Mera, S. |
| Ciudad: | Edinburgh |
| Filiación: | INRIA Nancy Grand Est, France LSV, ENS Cachan, INRIA, France Departamento de Computación, FCEyN, UBA, Argentina CONICET, Argentina |
| Palabras clave: | Computability and decidability; Information theory; Linguistics; Bisimulation; Expressive power; Heidelberg (CO); Hybrid logics; International (CO); Modal logics; Satisfiability (SAT) problems; Undecidability; Fuzzy logic |
| Año: | 2008 |
| Volumen: | 5110 LNAI |
| Página de inicio: | 56 |
| Página de fin: | 68 |
| DOI: | http://dx.doi.org/10.1007/978-3-540-69937-8_7 |
| Título revista: | 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008 |
| Título revista abreviado: | Lect. Notes Comput. Sci. |
| ISSN: | 03029743 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5110LNAI_n_p56_Areces |
Referencias:
- Blackburn, P., de Rijke, M., Venema, Y., (2001) Modal Logic, , Cambridge University Press, Cambridge
- Blackburn, P., Seligman, J., Hybrid languages (1995) Journal of Logic, Language and Information, 4, pp. 251-272
- Ebbinghaus, H., Flum, J., Thomas, W., (1984) Mathematical Logic, , Springer, Heidelberg
- Areces, C., Blackburn, P., Marx, M., Hybrid logics: Characterization, interpolation and complexity (2001) The Journal of Symbolic Logic, 66 (3), pp. 977-1010
- Borger, E., Grädel, E., Gurevich, Y., (1997) The classical decision problem, , Springer, Heidelberg
- Blackburn, P., Internalizing labelled deduction (2000) Journal of Logic and Computation, 10 (1), pp. 137-168
- van Benthem, J., An essay on sabotage and obstruction (2005) Mechanizing Mathematical Reasoning, pp. 268-276
- Gerbrandy, J., (2001) Bisimulations on Planet Kripke, , PhD thesis, University of Amsterdam, ILLC Dissertation series DS, 1999
Citas:
---------- APA ----------
Areces, C., Figueira, D., Figueira, S. & Mera, S. (2008) . Expressive power and decidability for memory logics. 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008, 5110 LNAI, 56-68.http://dx.doi.org/10.1007/978-3-540-69937-8_7
---------- CHICAGO ----------
Areces, C., Figueira, D., Figueira, S., Mera, S. "Expressive power and decidability for memory logics" . 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008 5110 LNAI (2008) : 56-68.http://dx.doi.org/10.1007/978-3-540-69937-8_7
---------- MLA ----------
Areces, C., Figueira, D., Figueira, S., Mera, S. "Expressive power and decidability for memory logics" . 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008, vol. 5110 LNAI, 2008, pp. 56-68.http://dx.doi.org/10.1007/978-3-540-69937-8_7
---------- VANCOUVER ----------
Areces, C., Figueira, D., Figueira, S., Mera, S. Expressive power and decidability for memory logics. Lect. Notes Comput. Sci. 2008;5110 LNAI:56-68.http://dx.doi.org/10.1007/978-3-540-69937-8_7
