Expressibility of the logic SOF on classes of structures of bounded FO types

We introduce a new property for classes of structures (or relational database instances), that we call bounded FO types. Then we prove that on such classes the expressive power of SOF collapses to rst order logic FO. As a consequence of this we prove that SOF is strictly included in SO.

Detalles Bibliográficos
Autores principales: Grosso, Alejandro, Turull Torres, José María
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2012
Materias:
Ciencias Informáticas
Theory of Computation
Finite Model Theory
Descriptive Complexity
Relational Machines
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/23807
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-23807
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Theory of Computation
Finite Model Theory
Descriptive Complexity
Relational Machines
spellingShingle Ciencias Informáticas
Theory of Computation
Finite Model Theory
Descriptive Complexity
Relational Machines
Grosso, Alejandro
Turull Torres, José María
Expressibility of the logic SOF on classes of structures of bounded FO types
topic_facet Ciencias Informáticas
Theory of Computation
Finite Model Theory
Descriptive Complexity
Relational Machines
description We introduce a new property for classes of structures (or relational database instances), that we call bounded FO types. Then we prove that on such classes the expressive power of SOF collapses to rst order logic FO. As a consequence of this we prove that SOF is strictly included in SO.
format Objeto de conferencia
Objeto de conferencia
author Grosso, Alejandro
Turull Torres, José María
author_facet Grosso, Alejandro
Turull Torres, José María
author_sort Grosso, Alejandro
title Expressibility of the logic SOF on classes of structures of bounded FO types
title_short Expressibility of the logic SOF on classes of structures of bounded FO types
title_full Expressibility of the logic SOF on classes of structures of bounded FO types
title_fullStr Expressibility of the logic SOF on classes of structures of bounded FO types
title_full_unstemmed Expressibility of the logic SOF on classes of structures of bounded FO types
title_sort expressibility of the logic sof on classes of structures of bounded fo types
publishDate 2012
url http://sedici.unlp.edu.ar/handle/10915/23807
work_keys_str_mv AT grossoalejandro expressibilityofthelogicsofonclassesofstructuresofboundedfotypes
AT turulltorresjosemaria expressibilityofthelogicsofonclassesofstructuresofboundedfotypes
bdutipo_str Repositorios
_version_ 1764820466253430786

Ejemplares similares