2026-07-22T14:20:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14495 2024-03-06T10:54:09Z ddc:004 open_access

On Deciding Linear Arithmetic Constraints Over p-adic Integers for All Primes Haase, Christoph Mansutti, Alessio linear arithmetic Büchi arithmetic p-adic numbers automatic structures Given an existential formula Φ of linear arithmetic over p-adic integers together with valuation constraints, we study the p-universality problem which consists of deciding whether Φ is satisfiable for all primes p, and the analogous problem for the closely related existential theory of Büchi arithmetic. Our main result is a coNEXP upper bound for both problems, together with a matching lower bound for existential Büchi arithmetic. On a technical level, our results are obtained from analysing properties of a certain class of p-automata, finite-state automata whose languages encode sets of tuples of natural numbers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christoph Haase and Alessio Mansutti 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.55 urn:nbn:de:0030-drops-144953 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.55 eng https://creativecommons.org/licenses/by/4.0/legalcode