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.

Guardado en:
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
Descripción
Sumario: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.

Ejemplares similares