2026-07-22T17:55:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9692 2024-03-06T10:44:50Z ddc:004 open_access

Dependency Concepts up to Equivalence Grädel, Erich Hoelzel, Matthias Logics of dependence and independence Team semantics Existential second-order logic Observational equivalence Expressive power Modern logics of dependence and independence are based on different variants of atomic dependency statements (such as dependence, exclusion, inclusion, or independence) and on team semantics: A formula is evaluated not with a single assignment of values to the free variables, but with a set of such assignments, called a team. In this paper we explore logics of dependence and independence where the atomic dependency statements cannot distinguish elements up to equality, but only up to a given equivalence relation (which may model observational indistinguishabilities, for instance between states of a computational process or between values obtained in an experiment). Our main goal is to analyse the power of such logics, by identifying equally expressive fragments of existential second-order logic or greatest fixed-point logic, with relations that are closed under the given equivalence. Using an adaptation of the Ehrenfeucht-Fraïssé method we further study conditions on the given equivalences under which these logics collapse to first-order logic, are equivalent to full existential second-order logic, or are strictly between first-order and existential second-order logic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erich Grädel and Matthias Hoelzel 2018 Is Part Of LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2018.25 urn:nbn:de:0030-drops-96921 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.25 eng https://creativecommons.org/licenses/by/3.0/legalcode