We prove that adding upwards closed first-order dependency atoms to first-order logic with team semantics does not increase its expressive power (with respect to sentences), and that the same remains true if we also add constancy atoms. As a consequence, the negations of functional dependence, conditional independence, inclusion and exclusion atoms can all be added to first-order logic without increasing its expressive power. Furthermore, we define a class of bounded upwards closed dependencies and we prove that unbounded dependencies cannot be defined in terms of bounded ones.

Upwards closed dependencies in team semantics

Galliani P
2015-01-01

Abstract

We prove that adding upwards closed first-order dependency atoms to first-order logic with team semantics does not increase its expressive power (with respect to sentences), and that the same remains true if we also add constancy atoms. As a consequence, the negations of functional dependence, conditional independence, inclusion and exclusion atoms can all be added to first-order logic without increasing its expressive power. Furthermore, we define a class of bounded upwards closed dependencies and we prove that unbounded dependencies cannot be defined in terms of bounded ones.
2015
2015
Dependence logic; Dependencies; Team semantics
Galliani, P
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0890540115000760-main (1).pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Copyright dell'editore
Dimensione 409.97 kB
Formato Adobe PDF
409.97 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2145649
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 12
social impact