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, Carlos Eduardo, Figueira, Diego Federico, Figueira, Santiago Daniel, Mera, Sergio Fernando
Publicado:	2008
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:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5110LNAI_n_p56_Areces 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	paper:paper_03029743_v5110LNAI_n_p56_Areces
record_format	dspace
spelling	paper:paper_03029743_v5110LNAI_n_p56_Areces2023-06-08T15:28:28Z Expressive power and decidability for memory logics Areces, Carlos Eduardo Figueira, Diego Federico Figueira, Santiago Daniel Mera, Sergio Fernando 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. 2008 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5110LNAI_n_p56_Areces 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, Carlos Eduardo Figueira, Diego Federico Figueira, Santiago Daniel Mera, Sergio Fernando 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.
author	Areces, Carlos Eduardo Figueira, Diego Federico Figueira, Santiago Daniel Mera, Sergio Fernando
author_facet	Areces, Carlos Eduardo Figueira, Diego Federico Figueira, Santiago Daniel Mera, Sergio Fernando
author_sort	Areces, Carlos Eduardo
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
publishDate	2008
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5110LNAI_n_p56_Areces http://hdl.handle.net/20.500.12110/paper_03029743_v5110LNAI_n_p56_Areces
work_keys_str_mv	AT arecescarloseduardo expressivepoweranddecidabilityformemorylogics AT figueiradiegofederico expressivepoweranddecidabilityformemorylogics AT figueirasantiagodaniel expressivepoweranddecidabilityformemorylogics AT merasergiofernando expressivepoweranddecidabilityformemorylogics
_version_	1768545555033620480

Expressive power and decidability for memory logics

Ejemplares similares