Expressive power and decidability for memory logics
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 exp...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2008
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 04017caa a22006137a 4500 | ||
|---|---|---|---|
| 001 | PAPER-5796 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203528.0 | ||
| 008 | 190411s2008 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-47749146194 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Areces, C. | |
| 245 | 1 | 0 | |a Expressive power and decidability for memory logics |
| 260 | |c 2008 | ||
| 270 | 1 | 0 | |m Areces, C.; INRIA Nancy Grand EstFrance |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Blackburn, P., de Rijke, M., Venema, Y., (2001) Modal Logic, , Cambridge University Press, Cambridge | ||
| 504 | |a Blackburn, P., Seligman, J., Hybrid languages (1995) Journal of Logic, Language and Information, 4, pp. 251-272 | ||
| 504 | |a Ebbinghaus, H., Flum, J., Thomas, W., (1984) Mathematical Logic, , Springer, Heidelberg | ||
| 504 | |a Areces, C., Blackburn, P., Marx, M., Hybrid logics: Characterization, interpolation and complexity (2001) The Journal of Symbolic Logic, 66 (3), pp. 977-1010 | ||
| 504 | |a Borger, E., Grädel, E., Gurevich, Y., (1997) The classical decision problem, , Springer, Heidelberg | ||
| 504 | |a Blackburn, P., Internalizing labelled deduction (2000) Journal of Logic and Computation, 10 (1), pp. 137-168 | ||
| 504 | |a van Benthem, J., An essay on sabotage and obstruction (2005) Mechanizing Mathematical Reasoning, pp. 268-276 | ||
| 504 | |a Gerbrandy, J., (2001) Bisimulations on Planet Kripke, , PhD thesis, University of Amsterdam, ILLC Dissertation series DS, 1999 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a INRIA Nancy Grand Est, France | ||
| 593 | |a LSV, ENS Cachan, INRIA, France | ||
| 593 | |a Departamento de Computación, FCEyN, UBA, Argentina | ||
| 593 | |a CONICET, Argentina | ||
| 690 | 1 | 0 | |a COMPUTABILITY AND DECIDABILITY |
| 690 | 1 | 0 | |a INFORMATION THEORY |
| 690 | 1 | 0 | |a LINGUISTICS |
| 690 | 1 | 0 | |a BISIMULATION |
| 690 | 1 | 0 | |a EXPRESSIVE POWER |
| 690 | 1 | 0 | |a HEIDELBERG (CO) |
| 690 | 1 | 0 | |a HYBRID LOGICS |
| 690 | 1 | 0 | |a INTERNATIONAL (CO) |
| 690 | 1 | 0 | |a MODAL LOGICS |
| 690 | 1 | 0 | |a SATISFIABILITY (SAT) PROBLEMS |
| 690 | 1 | 0 | |a UNDECIDABILITY |
| 690 | 1 | 0 | |a FUZZY LOGIC |
| 700 | 1 | |a Figueira, D. | |
| 700 | 1 | |a Figueira, S. | |
| 700 | 1 | |a Mera, S. | |
| 711 | 2 | |c Edinburgh |d 1 July 2008 through 4 July 2008 |g Código de la conferencia: 72694 | |
| 773 | 0 | |d 2008 |g v. 5110 LNAI |h pp. 56-68 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 3540699368 |z 9783540699361 |t 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-47749146194&doi=10.1007%2f978-3-540-69937-8_7&partnerID=40&md5=a95b9787b5fd0171e965aef7f3fe4769 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/978-3-540-69937-8_7 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v5110LNAI_n_p56_Areces |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5110LNAI_n_p56_Areces |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v5110LNAI_n_p56_Areces |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 66749 | ||