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.STACS.2017.1
URN: urn:nbn:de:0030-drops-70333
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7033/
Go to the corresponding LIPIcs Volume Portal

Kontinen, Juha

Computational Aspects of Logics in Team Semantics (Tutorial)

pdf-format:
LIPIcs-STACS-2017-1.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{kontinen:LIPIcs:2017:7033,
  author =	{Juha Kontinen},
  title =	{{Computational Aspects of Logics in Team Semantics (Tutorial)}},
  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 =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7033},
  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}
}

Keywords: team semantics, dependence logic, model checking, satisfiability problem, team bisimulation
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

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