Polyteam Semantics

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

Team semantics is the mathematical framework of modern logics of dependence and independence in which formulae are interpreted by sets of assignments (teams) instead of single assignments as in first-order logic. In order to deepen the fruitful interplay between team semantics and database dependency theory, we define "Polyteam Semantics" in which formulae are evaluated over a family of teams. We begin by defining a novel polyteam variant of dependence atoms and give a finite axiomatisation for the associated implication problem. We also characterise the expressive power of poly-dependence logic by properties of polyteams that are downward closed and definable in existential second-order logic (ESO). The analogous result is shown to hold for poly-independence logic and all ESO-definable properties.
Original languageEnglish
Title of host publicationLogical Foundations of Computer Science
EditorsSergei Artemov, Anil Nerode
Number of pages21
Volume2018
PublisherSpringer
Publication date2018
Pages190–210
ISBN (Print)978-3-319-72055-5
ISBN (Electronic)978-3-319-72056-2
DOIs
Publication statusPublished - 2018
MoE publication typeA4 Article in conference proceedings
EventLogical Foundations of Computer Science 2018 - Deerfield Beach, United States
Duration: 8 Jan 201811 Jan 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10703
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fields of Science

  • cs.LO
  • 111 Mathematics
  • 112 Statistics and probability

Cite this