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

Chistikov, Dmitry ; Haase, Christoph

On the Power of Ordering in Linear Arithmetic Theories

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

Abstract

We study the problems of deciding whether a relation definable by a first-order formula in linear rational or linear integer arithmetic with an order relation is definable in absence of the order relation. Over the integers, this problem was shown decidable by Choffrut and Frigeri [Discret. Math. Theor. C., 12(1), pp. 21 - 38, 2010], albeit with non-elementary time complexity. Our contribution is to establish a full geometric characterisation of those sets definable without order which in turn enables us to prove coNP-completeness of this problem over the rationals and to establish an elementary upper bound over the integers. We also provide a complementary Π₂^P lower bound for the integer case that holds even in a fixed dimension. This lower bound is obtained by showing that universality for ultimately periodic sets, i.e., semilinear sets in dimension one, is Π₂^P-hard, which resolves an open problem of Huynh [Elektron. Inf.verarb. Kybern., 18(6), pp. 291 - 338, 1982].

BibTeX - Entry

@InProceedings{chistikov_et_al:LIPIcs:2020:12526,
  author =	{Dmitry Chistikov and Christoph Haase},
  title =	{{On the Power of Ordering in Linear Arithmetic Theories}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{119:1--119:15},
  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/12526},
  URN =		{urn:nbn:de:0030-drops-125265},
  doi =		{10.4230/LIPIcs.ICALP.2020.119},
  annote =	{Keywords: logical definability, linear arithmetic theories, semi linear sets, ultimately periodic sets, numerical semigroups}
}

Keywords: logical definability, linear arithmetic theories, semi linear sets, ultimately periodic sets, numerical semigroups
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