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:
| Autores principales: | Grosso, Alejandro, Turull Torres, José María |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2012
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/23807 |
| Aporte de: |
Ejemplares similares
-
L-rigid Databases and the Expressibility of Incomplete Relational Query Languages
por: Turull Torres, José María
Publicado: (1998) -
Complex systems dynamics : an introduction to automata networks /
por: Weisbuch, G.
Publicado: (1991) -
Capturing relational NEXPTIME with a fragment of existential third order logic
por: Turull Torres, José María
Publicado: (2015) -
Information, randomness & incompleteness : papers on algorithmic information theory /
por: Chaitin, Gregory J.
Publicado: (1987) -
Capturing relational NEXPTIME with a fragment of existential third order logic
por: Turull Torres, José María
Publicado: (2015)