DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.21

Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions

Authors: Hera Brown and Jakub Konieczny

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

We study the extension of Presburger arithmetic by the class of sub-polynomial Hardy field functions, and show the majority of these extensions to be undecidable. More precisely, we show that the theory Th(ℤ; < , +, ⌊f⌉), where f is a Hardy field function and ⌊⋅⌉ the nearest integer operator, is undecidable when f grows polynomially faster than x. Further, we show that when f grows sub-linearly quickly, but still as fast as some polynomial, the theory Th(ℤ; < , +, ⌊f⌉) is undecidable.

Cite as

Hera Brown and Jakub Konieczny. Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brown_et_al:LIPIcs.STACS.2026.21,
  author =	{Brown, Hera and Konieczny, Jakub},
  title =	{{Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.21},
  URN =		{urn:nbn:de:0030-drops-255103},
  doi =		{10.4230/LIPIcs.STACS.2026.21},
  annote =	{Keywords: Arithmetic theories, Hardy fields, Undecidability}
}

Search Results

Documents authored by Brown, Hera

Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions

Abstract

Cite as

Thanks for your feedback!

Could not send message