On the existential theories of Büchi arithmetic and linear p-adic fields

On the existential theories of Büchi arithmetic and linear p-adic fields

We consider the complexity of the satisfiability problems for the existential fragment of Büchi arithmetic and for the existential fragment of linear arithmetic over p-adic fields. Our main results are that both problems are NP-complete. The NP upper bound for existential linear arithmetic over p-ad...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Guépin, F, Haase, C, Worrell, J
Formáid:	Conference item
Foilsithe / Cruthaithe:	IEEE 2019

Míreanna comhchosúla

On the expressiveness of Büchi arithmetic
de réir: Haase, C, et al.
Foilsithe / Cruthaithe: (2021)

On deciding linear arithmetic constraints over -adic integers for all primes
de réir: Haase, C, et al.
Foilsithe / Cruthaithe: (2021)

Rational number arithmetic by Parallel P-adic Algorithms /
de réir: 284588 Limongeli, Carla, et al.

Almost Linear Büchi Automata
de réir: Tomáš Babiak, et al.
Foilsithe / Cruthaithe: (2009-11-01)

Markov chains and unambiguous Büchi automata
de réir: Baier, C, et al.
Foilsithe / Cruthaithe: (2016)

Markov Chains and Unambiguous Büchi Automata
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2016)

On sections of arithmetic fundamental groups of open $p$-adic annuli
de réir: Saïdi, Mohamed
Foilsithe / Cruthaithe: (2022-03-01)

On the p-adic zeros of the Tribonacci sequence
de réir: Bilu, Y, et al.
Foilsithe / Cruthaithe: (2023)

The implementation of p-adic conversion of rational numbers and its arithmetic operations /
de réir: Muhammad Saiful Adham Shukor, 1992-, et al.
Foilsithe / Cruthaithe: (2014)

Coleman–Weinberg potential in p-adic field theory
de réir: Dmitry S. Ageev, et al.
Foilsithe / Cruthaithe: (2020-09-01)

Parallel Implementation of Exact Matrix Computation Using Multiple P-adic Arithmetic
de réir: Xinkai Li, et al.
Foilsithe / Cruthaithe: (2013-07-01)

Pemodelan logika pemeriksaan temporal linier dengan buchi automata=Logic checking linear temporal with buchi automata
de réir: Perpustakaan UGM, i-lib
Foilsithe / Cruthaithe: (2005)

Büchi AG
de réir: David Spichiger
Foilsithe / Cruthaithe: (2023-03-01)

Büchi AG
de réir: David Spichiger
Foilsithe / Cruthaithe: (2023-03-01)

Büchi AG
de réir: David Spichiger
Foilsithe / Cruthaithe: (2023-03-01)

Büchi AG
de réir: David Spichiger
Foilsithe / Cruthaithe: (2023-08-01)

Surfaces and p-adic fields
de réir: Gropper, N
Foilsithe / Cruthaithe: (2022)

Geometric decision procedures and the VC dimension of linear arithmetic theories
de réir: Chistikov, D, et al.
Foilsithe / Cruthaithe: (2022)

p-Adic Fractional Pseudodifferential Equations and Sobolev Type Spaces over p-Adic Fields
de réir: Bo Wu
Foilsithe / Cruthaithe: (2013-01-01)

Topics in the theory of p-adic heights on elliptic curves
de réir: Bianchi, F
Foilsithe / Cruthaithe: (2019)

Duality theory of $p$-adic Hopf algebras
de réir: Tomoki Mihara
Foilsithe / Cruthaithe: (2021-01-01)

P-adic numbers, P-adic analysis and zeta-functions /
de réir: 465056 Koblitz, Neal
Foilsithe / Cruthaithe: (1977)

Büchi objectives in countable MDPs
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2019)

Model theory of finite-by-Presburger Abelian groups and finite extensions of $p$-adic fields
de réir: Derakhshan, J, et al.
Foilsithe / Cruthaithe: (2016)

Reconstructing D-cap from p-adic Hodge theory
de réir: Wiersig, F
Foilsithe / Cruthaithe: (2024)

Some new directions in p-adic Hodge theory
de réir: Kedlaya, Kiran S.
Foilsithe / Cruthaithe: (2012)

$p$-ADIC HODGE THEORY FOR RIGID-ANALYTIC VARIETIES
de réir: PETER SCHOLZE
Foilsithe / Cruthaithe: (2013-01-01)

Nearly Quadratic Mappings over p-Adic Fields
de réir: M. Eshaghi Gordji, et al.
Foilsithe / Cruthaithe: (2012-01-01)

On dynamical systems induced by p-adic number fields
de réir: Ilwoo Cho
Foilsithe / Cruthaithe: (2015-01-01)

Cell decomposition for semiaffine structures on p-adic fields
de réir: Eva Leenknegt
Foilsithe / Cruthaithe: (2012-08-01)

On the decidability of the field of maximal abelian extension of p-adic numbers
de réir: Wang, C
Foilsithe / Cruthaithe: (2018)

The logical strength of Büchi's decidability theorem
de réir: Kolodziejczyk, L, et al.
Foilsithe / Cruthaithe: (2019)

The logical strength of Büchi's decidability theorem
de réir: Kolodziejczyk, L, et al.
Foilsithe / Cruthaithe: (2016)

Learn with SAT to Minimize Büchi Automata
de réir: Stephan Barth, et al.
Foilsithe / Cruthaithe: (2012-10-01)

Construction of p-Adic Gibbs Measure for p-Adic λ-Ising Model
de réir: Mutlay Dogan
Foilsithe / Cruthaithe: (2017-09-01)

Computing p-adic L-functions of totally real fields
de réir: Lauder, A, et al.
Foilsithe / Cruthaithe: (2021)

Mirror symmetry and the K theory of a p-adic group
de réir: Vaintrob, Dmitry
Foilsithe / Cruthaithe: (2016)

$p$ -ADIC HODGE THEORY FOR RIGID-ANALYTIC VARIETIES – CORRIGENDUM
de réir: PETER SCHOLZE
Foilsithe / Cruthaithe: (2016-01-01)

Valued fields: p-adic numbers as a case study
de réir: Song, Ruiqi
Foilsithe / Cruthaithe: (2023)

Oxetane Synthesis through the Paternò-Büchi Reaction
de réir: Maurizio D'Auria, et al.
Foilsithe / Cruthaithe: (2013-09-01)