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.ICALP.2020.112
URN: urn:nbn:de:0030-drops-125197
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12519/
Go to the corresponding LIPIcs Volume Portal

Benedikt, Michael ; Kostylev, Egor V. ; Tan, Tony

Two Variable Logic with Ultimately Periodic Counting

pdf-format:
LIPIcs-ICALP-2020-112.pdf (0.7 MB)

Abstract

We consider the extension of FO² with quantifiers that state that the number of elements where a formula holds should belong to a given ultimately periodic set. We show that both satisfiability and finite satisfiability of the logic are decidable. We also show that the spectrum of any sentence is definable in Presburger arithmetic. In the process we present several refinements to the "biregular graph method". In this method, decidability issues concerning two-variable logics are reduced to questions about Presburger definability of integer vectors associated with partitioned graphs, where nodes in a partition satisfy certain constraints on their in- and out-degrees.

BibTeX - Entry

@InProceedings{benedikt_et_al:LIPIcs:2020:12519,
  author =	{Michael Benedikt and Egor V. Kostylev and Tony Tan},
  title =	{{Two Variable Logic with Ultimately Periodic Counting}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{112:1--112:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12519},
  URN =		{urn:nbn:de:0030-drops-125197},
  doi =		{10.4230/LIPIcs.ICALP.2020.112},
  annote =	{Keywords: Presburger Arithmetic, Two-variable logic}
}

Keywords: Presburger Arithmetic, Two-variable logic
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

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