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...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Guépin, F, Haase, C, Worrell, J
Fformat:	Conference item
Cyhoeddwyd:	IEEE 2019

Eitemau Tebyg

On the expressiveness of Büchi arithmetic
gan: Haase, C, et al.
Cyhoeddwyd: (2021)

On deciding linear arithmetic constraints over -adic integers for all primes
gan: Haase, C, et al.
Cyhoeddwyd: (2021)

Rational number arithmetic by Parallel P-adic Algorithms /
gan: 284588 Limongeli, Carla, et al.

Almost Linear Büchi Automata
gan: Tomáš Babiak, et al.
Cyhoeddwyd: (2009-11-01)

Markov chains and unambiguous Büchi automata
gan: Baier, C, et al.
Cyhoeddwyd: (2016)

Markov Chains and Unambiguous Büchi Automata
gan: Kiefer, S, et al.
Cyhoeddwyd: (2016)

On sections of arithmetic fundamental groups of open $p$-adic annuli
gan: Saïdi, Mohamed
Cyhoeddwyd: (2022-03-01)

On the p-adic zeros of the Tribonacci sequence
gan: Bilu, Y, et al.
Cyhoeddwyd: (2023)

The implementation of p-adic conversion of rational numbers and its arithmetic operations /
gan: Muhammad Saiful Adham Shukor, 1992-, et al.
Cyhoeddwyd: (2014)

Coleman–Weinberg potential in p-adic field theory
gan: Dmitry S. Ageev, et al.
Cyhoeddwyd: (2020-09-01)

Parallel Implementation of Exact Matrix Computation Using Multiple P-adic Arithmetic
gan: Xinkai Li, et al.
Cyhoeddwyd: (2013-07-01)

Pemodelan logika pemeriksaan temporal linier dengan buchi automata=Logic checking linear temporal with buchi automata
gan: Perpustakaan UGM, i-lib
Cyhoeddwyd: (2005)

Büchi AG
gan: David Spichiger
Cyhoeddwyd: (2023-03-01)

Büchi AG
gan: David Spichiger
Cyhoeddwyd: (2023-03-01)

Büchi AG
gan: David Spichiger
Cyhoeddwyd: (2023-03-01)

Büchi AG
gan: David Spichiger
Cyhoeddwyd: (2023-08-01)

Surfaces and p-adic fields
gan: Gropper, N
Cyhoeddwyd: (2022)

Geometric decision procedures and the VC dimension of linear arithmetic theories
gan: Chistikov, D, et al.
Cyhoeddwyd: (2022)

p-Adic Fractional Pseudodifferential Equations and Sobolev Type Spaces over p-Adic Fields
gan: Bo Wu
Cyhoeddwyd: (2013-01-01)

Topics in the theory of p-adic heights on elliptic curves
gan: Bianchi, F
Cyhoeddwyd: (2019)

Duality theory of $p$-adic Hopf algebras
gan: Tomoki Mihara
Cyhoeddwyd: (2021-01-01)

P-adic numbers, P-adic analysis and zeta-functions /
gan: 465056 Koblitz, Neal
Cyhoeddwyd: (1977)

Büchi objectives in countable MDPs
gan: Kiefer, S, et al.
Cyhoeddwyd: (2019)

Model theory of finite-by-Presburger Abelian groups and finite extensions of $p$-adic fields
gan: Derakhshan, J, et al.
Cyhoeddwyd: (2016)

Reconstructing D-cap from p-adic Hodge theory
gan: Wiersig, F
Cyhoeddwyd: (2024)

Some new directions in p-adic Hodge theory
gan: Kedlaya, Kiran S.
Cyhoeddwyd: (2012)

$p$-ADIC HODGE THEORY FOR RIGID-ANALYTIC VARIETIES
gan: PETER SCHOLZE
Cyhoeddwyd: (2013-01-01)

Nearly Quadratic Mappings over p-Adic Fields
gan: M. Eshaghi Gordji, et al.
Cyhoeddwyd: (2012-01-01)

On dynamical systems induced by p-adic number fields
gan: Ilwoo Cho
Cyhoeddwyd: (2015-01-01)

Cell decomposition for semiaffine structures on p-adic fields
gan: Eva Leenknegt
Cyhoeddwyd: (2012-08-01)

On the decidability of the field of maximal abelian extension of p-adic numbers
gan: Wang, C
Cyhoeddwyd: (2018)

The logical strength of Büchi's decidability theorem
gan: Kolodziejczyk, L, et al.
Cyhoeddwyd: (2019)

The logical strength of Büchi's decidability theorem
gan: Kolodziejczyk, L, et al.
Cyhoeddwyd: (2016)

Learn with SAT to Minimize Büchi Automata
gan: Stephan Barth, et al.
Cyhoeddwyd: (2012-10-01)

Construction of p-Adic Gibbs Measure for p-Adic λ-Ising Model
gan: Mutlay Dogan
Cyhoeddwyd: (2017-09-01)

Computing p-adic L-functions of totally real fields
gan: Lauder, A, et al.
Cyhoeddwyd: (2021)

Mirror symmetry and the K theory of a p-adic group
gan: Vaintrob, Dmitry
Cyhoeddwyd: (2016)

$p$ -ADIC HODGE THEORY FOR RIGID-ANALYTIC VARIETIES – CORRIGENDUM
gan: PETER SCHOLZE
Cyhoeddwyd: (2016-01-01)

Valued fields: p-adic numbers as a case study
gan: Song, Ruiqi
Cyhoeddwyd: (2023)

Oxetane Synthesis through the Paternò-Büchi Reaction
gan: Maurizio D'Auria, et al.
Cyhoeddwyd: (2013-09-01)