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...

Descripción completa

Detalles Bibliográficos
Autores principales: Areces, C., Figueira, D., Figueira, S., Mera, S.
Formato: SER
Materias:
Computability and decidability
Information theory
Linguistics
Bisimulation
Expressive power
Heidelberg (CO)
Hybrid logics
International (CO)
Modal logics
Satisfiability (SAT) problems
Undecidability
Fuzzy logic
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v5110LNAI_n_p56_Areces
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
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

Ejemplares similares