2026-07-20T05:25:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4202 2024-03-06T10:34:53Z ddc:004 open_access

Hierarchies in independence logic Galliani, Pietro Hannula, Miika Kontinen, Juha Existential second-order logic Independence logic Inclusion logic Expressiveness hierarchies 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pietro Galliani and Miika Hannula and Juha Kontinen 2013 Is Part Of LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2013.263 urn:nbn:de:0030-drops-42021 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.263 eng https://creativecommons.org/licenses/by/3.0/legalcode