License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2013.263
URN: urn:nbn:de:0030-drops-42021
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4202/
Go to the corresponding LIPIcs Volume Portal

Galliani, Pietro ; Hannula, Miika ; Kontinen, Juha

Hierarchies in independence logic

pdf-format:
22.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{galliani_et_al:LIPIcs:2013:4202,
  author =	{Pietro Galliani and Miika Hannula and Juha Kontinen},
  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 =	{Simona Ronchi Della Rocca},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4202},
  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}
}

Keywords: Existential second-order logic, Independence logic, Inclusion logic, Expressiveness hierarchies
Collection: Computer Science Logic 2013 (CSL 2013)
Issue Date: 2013
Date of publication: 02.09.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI