DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2013.263

Hierarchies in independence logic

Authors: Pietro Galliani, Miika Hannula, and Juha Kontinen

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract

We study the expressive power of fragments of inclusion and independence logic defined either by restricting the number of universal quantifiers or the arity of inclusion and independence atoms in formulas. Assuming the so-called lax semantics for these logics, we relate these fragments of inclusion and independence logic to familiar sublogics of existential second-order logic. We also show that, with respect to the stronger strict semantics, inclusion logic is equivalent to existential second-order logic.

Cite as

Pietro Galliani, Miika Hannula, and Juha Kontinen. Hierarchies in independence logic. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 263-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{galliani_et_al:LIPIcs.CSL.2013.263,
  author =	{Galliani, Pietro and Hannula, Miika and Kontinen, Juha},
  title =	{{Hierarchies in independence logic}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{263--280},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.263},
  URN =		{urn:nbn:de:0030-drops-42021},
  doi =		{10.4230/LIPIcs.CSL.2013.263},
  annote =	{Keywords: Existential second-order logic, Independence logic, Inclusion logic, Expressiveness hierarchies}
}

Document

DOI: 10.4230/LIPIcs.CSL.2013.281

Inclusion Logic and Fixed Point Logic

Authors: Pietro Galliani and Lauri Hella

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract

We investigate the properties of Inclusion Logic, that is, First Order Logic with Team Semantics extended with inclusion dependencies. We prove that Inclusion Logic is equivalent to Greatest Fixed Point Logic, and we prove that all union-closed first-order definable properties of relations are definable in it. We also provide an Ehrenfeucht-Fraïssé game for Inclusion Logic, and give an example illustrating its use.

Cite as

Pietro Galliani and Lauri Hella. Inclusion Logic and Fixed Point Logic. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 281-295, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{galliani_et_al:LIPIcs.CSL.2013.281,
  author =	{Galliani, Pietro and Hella, Lauri},
  title =	{{Inclusion Logic and Fixed Point Logic}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{281--295},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.281},
  URN =		{urn:nbn:de:0030-drops-42031},
  doi =		{10.4230/LIPIcs.CSL.2013.281},
  annote =	{Keywords: Dependence Logic, Team Semantics, Fixpoint Logic, Inclusion}
}

Search Results

Documents authored by Galliani, Pietro

Hierarchies in independence logic

Abstract

Cite as

Inclusion Logic and Fixed Point Logic

Abstract

Cite as

Thanks for your feedback!

Could not send message