Counting in Team Semantics

Authors Erich Grädel, Stefan Hegselmann



PDF
Thumbnail PDF

File

LIPIcs.CSL.2016.35.pdf
  • Filesize: 0.5 MB
  • 18 pages

Document Identifiers

Author Details

Erich Grädel
Stefan Hegselmann

Cite AsGet BibTex

Erich Grädel and Stefan Hegselmann. Counting in Team Semantics. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CSL.2016.35

Abstract

We explore several counting constructs for logics with team semantics. Counting is an important task in numerous applications, but with a somewhat delicate relationship to logic. Team semantics on the other side is the mathematical basis of modern logics of dependence and independence, in which formulae are evaluated not for a single assignment of values to variables, but for a set of such assignments. It is therefore interesting to ask what kind of counting constructs are adequate in this context, and how such constructs influence the expressive power, and the model-theoretic and algorithmic properties of logics with team semantics. Due to the second-order features of team semantics there is a rich variety of potential counting constructs. Here we study variations of two main ideas: forking atoms and counting quantifiers. Forking counts how many different values for a tuple w occur in assignments with coinciding values for v. We call this the forking degree of bar v with respect to bar w. Forking is powerful enough to capture many of the previously studied atomic dependency properties. In particular we exhibit logics with forking atoms that have, respectively, precisely the power of dependence logic and independence logic. Our second approach uses counting quantifiers E^{geq mu} of a similar kind as used in logics with Tarski semantics. The difference is that these quantifiers are now applied to teams of assignments that may give different values to mu. We show that, on finite structures, there is an intimate connection between inclusion logic with counting quantifiers and FPC, fixed-point logic with counting, which is a logic of fundamental importance for descriptive complexity theory. For sentences, the two logics have the same expressive power. Our analysis is based on a new variant of model-checking games, called threshold safety games, on a trap condition for such games, and on game interpretations.
Keywords
  • logics with counting
  • team semantics
  • fixed-point logic with counting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. A. Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2(1):8-21, 2015. Google Scholar
  2. A. Durand, J. Ebbing, J. Kontinen, and H. Vollmer. Dependence logic with a majority quantifier. In Proceedings of FSTTCS 2011, pages 252-263, 2011. Google Scholar
  3. F. Engström. Generalized quantifiers in dependence logic. Journal of Logic, Language, and Information, 2012. Google Scholar
  4. P. Galliani. Inclusion and exclusion in team semantics - on some logics of imperfect information. Annals of Pure and Applied Logic, 163:68-84, 2012. Google Scholar
  5. P. Galliani and L. Hella. Inclusion logic and fixed-point logic. In Computer Science Logic 2013, pages 281-295, 2013. Google Scholar
  6. E. Grädel. Games for inclusion logic and fixed-point logic. In S. Abramsky et al., editor, Dependence Logic. Theory and Applications. Birkhäuser, 2016. Google Scholar
  7. E. Grädel and J. Väänänen. Dependence and independence. Studia Logica, 101(2):399-410, 2013. Google Scholar
  8. Y. Gurevich and S. Shelah. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic, 32:265-280, 1986. Google Scholar
  9. W. Hodges. Model Theory. Cambridge University Press, 1993. Google Scholar
  10. W. Hodges. Compositional semantics for a logic of imperfect information. Logic Journal of IGPL, 5:539-563, 1997. Google Scholar
  11. N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86-104, 1986. Google Scholar
  12. J. Kontinen and J. Väänänen. On definability in dependence logic. Journal of Logic, Language, and Information, 18:317-241, 2009. Google Scholar
  13. S. Kreutzer. Expressive equivalence of least and inflationary fixed point logic. Annals of Pure and Applied Logic, 130:61-78, 2004. Google Scholar
  14. R. Rönnholm. Capturing k-ary existential second-order logic with k-ary inclusion-exclusion logic. arXiv:1502.05632v2, 2015. Google Scholar
  15. J. Väänänen. Dependence Logic. Cambridge University Press, 2007. Google Scholar
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