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...
Autores principales: | , , , |
---|---|
Formato: | SER |
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03029743_v5110LNAI_n_p56_Areces |
Aporte de: |
id |
todo:paper_03029743_v5110LNAI_n_p56_Areces |
---|---|
record_format |
dspace |
spelling |
todo:paper_03029743_v5110LNAI_n_p56_Areces2023-10-03T15:19:05Z Expressive power and decidability for memory logics Areces, C. Figueira, D. Figueira, S. Mera, S. Computability and decidability Information theory Linguistics Bisimulation Expressive power Heidelberg (CO) Hybrid logics International (CO) Modal logics Satisfiability (SAT) problems Undecidability Fuzzy logic 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. Fil:Areces, C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Figueira, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Mera, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v5110LNAI_n_p56_Areces |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
topic |
Computability and decidability Information theory Linguistics Bisimulation Expressive power Heidelberg (CO) Hybrid logics International (CO) Modal logics Satisfiability (SAT) problems Undecidability Fuzzy logic |
spellingShingle |
Computability and decidability Information theory Linguistics Bisimulation Expressive power Heidelberg (CO) Hybrid logics International (CO) Modal logics Satisfiability (SAT) problems Undecidability Fuzzy logic Areces, C. Figueira, D. Figueira, S. Mera, S. Expressive power and decidability for memory logics |
topic_facet |
Computability and decidability Information theory Linguistics Bisimulation Expressive power Heidelberg (CO) Hybrid logics International (CO) Modal logics Satisfiability (SAT) problems Undecidability Fuzzy logic |
description |
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. |
format |
SER |
author |
Areces, C. Figueira, D. Figueira, S. Mera, S. |
author_facet |
Areces, C. Figueira, D. Figueira, S. Mera, S. |
author_sort |
Areces, C. |
title |
Expressive power and decidability for memory logics |
title_short |
Expressive power and decidability for memory logics |
title_full |
Expressive power and decidability for memory logics |
title_fullStr |
Expressive power and decidability for memory logics |
title_full_unstemmed |
Expressive power and decidability for memory logics |
title_sort |
expressive power and decidability for memory logics |
url |
http://hdl.handle.net/20.500.12110/paper_03029743_v5110LNAI_n_p56_Areces |
work_keys_str_mv |
AT arecesc expressivepoweranddecidabilityformemorylogics AT figueirad expressivepoweranddecidabilityformemorylogics AT figueiras expressivepoweranddecidabilityformemorylogics AT meras expressivepoweranddecidabilityformemorylogics |
_version_ |
1807320973915979776 |