3 Search Results for "Väänanen, Jouko"

Document
DOI: 10.4230/LIPIcs.CSL.2018.25
Dependency Concepts up to Equivalence

Authors: Erich Grädel and Matthias Hoelzel

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
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.
Cite as

Erich Grädel and Matthias Hoelzel. Dependency Concepts up to Equivalence. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 25:1-25:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gradel_et_al:LIPIcs.CSL.2018.25,
  author =	{Gr\"{a}del, Erich and Hoelzel, Matthias},
  title =	{{Dependency Concepts up to Equivalence}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{25:1--25:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.25},
  URN =		{urn:nbn:de:0030-drops-96921},
  doi =		{10.4230/LIPIcs.CSL.2018.25},
  annote =	{Keywords: Logics of dependence and independence, Team semantics, Existential second-order logic, Observational equivalence, Expressive power}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2017.1
Computational Aspects of Logics in Team Semantics (Tutorial)

Authors: Juha Kontinen

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Team Semantics is a logical framework for the study of various dependency notions that are important in many areas of science. The starting point of this research is marked by the publication of the monograph Dependence Logic (Jouko Väänänen, 2007) in which first-order dependence logic is developed and studied. Since then team semantics has evolved into a flexible framework in which numerous logics have been studied. Much of the work in team semantics has so far focused on results concerning either axiomatic characterizations or the expressive power and computational aspects of various logics. This tutorial provides an introduction to team semantics with a focus on results regarding expressivity and computational aspects of the most prominent logics of the area. In particular, we discuss dependence, independence and inclusion logics in first-order, propositional, and modal team semantics. We show that first-order dependence and independence logic are equivalent with existential second-order logic and inclusion logic with greatest fixed point logic. In the propositional and modal settings we characterize the expressive power of these logics by so-called team bisimulations and determine the complexity of their model checking and satisfiability problems.
Cite as

Juha Kontinen. Computational Aspects of Logics in Team Semantics (Tutorial). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kontinen:LIPIcs.STACS.2017.1,
  author =	{Kontinen, Juha},
  title =	{{Computational Aspects of Logics in Team Semantics}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.1},
  URN =		{urn:nbn:de:0030-drops-70333},
  doi =		{10.4230/LIPIcs.STACS.2017.1},
  annote =	{Keywords: team semantics, dependence logic, model checking, satisfiability problem, team bisimulation}
}
Document
DOI: 10.4230/DagRep.3.2.45
Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071)

Authors: Samson Abramsky, Juha Kontinen, Jouko Väänanen, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 3, Issue 2 (2013)

Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 13071 "Dependence Logic: Theory and Applications". The seminar brought together researchers from different areas such as mathematical logic, quantum mechanics, statistics, social choice theory, and theoretical computer science. A key objective of the seminar was to bring together, for the first time, researchers working in dependence logic and in the application areas so that they can communicate state-of-the-art advances and embark on a systematic interaction.
Cite as

Samson Abramsky, Juha Kontinen, Jouko Väänanen, and Heribert Vollmer. Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071). In Dagstuhl Reports, Volume 3, Issue 2, pp. 45-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{abramsky_et_al:DagRep.3.2.45,
  author =	{Abramsky, Samson and Kontinen, Juha and V\"{a}\"{a}nanen, Jouko and Vollmer, Heribert},
  title =	{{Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071)}},
  pages =	{45--54},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{2},
  editor =	{Abramsky, Samson and Kontinen, Juha and V\"{a}\"{a}nanen, Jouko and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.2.45},
  URN =		{urn:nbn:de:0030-drops-40127},
  doi =		{10.4230/DagRep.3.2.45},
  annote =	{Keywords: Data structures, Algorithms, Complexity, Verification, Logic}
}
  • Refine by Author
  • 2 Kontinen, Juha
  • 1 Abramsky, Samson
  • 1 Grädel, Erich
  • 1 Hoelzel, Matthias
  • 1 Vollmer, Heribert
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Logic

  • Refine by Keyword
  • 1 Algorithms
  • 1 Complexity
  • 1 Data structures
  • 1 Existential second-order logic
  • 1 Expressive power
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2013
  • 1 2017
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact