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

Бүрэн тодорхойлолт

Номзүйн дэлгэрэнгүй
Үндсэн зохиолчид:	Guépin, F, Haase, C, Worrell, J
Формат:	Conference item
Хэвлэсэн:	IEEE 2019

Ижил төстэй зүйлс

On the expressiveness of Büchi arithmetic
-н: Haase, C, зэрэг
Хэвлэсэн: (2021)

On deciding linear arithmetic constraints over -adic integers for all primes
-н: Haase, C, зэрэг
Хэвлэсэн: (2021)

Rational number arithmetic by Parallel P-adic Algorithms /
-н: 284588 Limongeli, Carla, зэрэг

Almost Linear Büchi Automata
-н: Tomáš Babiak, зэрэг
Хэвлэсэн: (2009-11-01)

Markov chains and unambiguous Büchi automata
-н: Baier, C, зэрэг
Хэвлэсэн: (2016)

Markov Chains and Unambiguous Büchi Automata
-н: Kiefer, S, зэрэг
Хэвлэсэн: (2016)

On sections of arithmetic fundamental groups of open $p$-adic annuli
-н: Saïdi, Mohamed
Хэвлэсэн: (2022-03-01)

On the p-adic zeros of the Tribonacci sequence
-н: Bilu, Y, зэрэг
Хэвлэсэн: (2023)

The implementation of p-adic conversion of rational numbers and its arithmetic operations /
-н: Muhammad Saiful Adham Shukor, 1992-, зэрэг
Хэвлэсэн: (2014)

Coleman–Weinberg potential in p-adic field theory
-н: Dmitry S. Ageev, зэрэг
Хэвлэсэн: (2020-09-01)

Parallel Implementation of Exact Matrix Computation Using Multiple P-adic Arithmetic
-н: Xinkai Li, зэрэг
Хэвлэсэн: (2013-07-01)

Pemodelan logika pemeriksaan temporal linier dengan buchi automata=Logic checking linear temporal with buchi automata
-н: Perpustakaan UGM, i-lib
Хэвлэсэн: (2005)

Büchi AG
-н: David Spichiger
Хэвлэсэн: (2023-03-01)

Büchi AG
-н: David Spichiger
Хэвлэсэн: (2023-03-01)

Büchi AG
-н: David Spichiger
Хэвлэсэн: (2023-03-01)

Büchi AG
-н: David Spichiger
Хэвлэсэн: (2023-08-01)

Surfaces and p-adic fields
-н: Gropper, N
Хэвлэсэн: (2022)

Geometric decision procedures and the VC dimension of linear arithmetic theories
-н: Chistikov, D, зэрэг
Хэвлэсэн: (2022)

p-Adic Fractional Pseudodifferential Equations and Sobolev Type Spaces over p-Adic Fields
-н: Bo Wu
Хэвлэсэн: (2013-01-01)

Topics in the theory of p-adic heights on elliptic curves
-н: Bianchi, F
Хэвлэсэн: (2019)

Duality theory of $p$-adic Hopf algebras
-н: Tomoki Mihara
Хэвлэсэн: (2021-01-01)

P-adic numbers, P-adic analysis and zeta-functions /
-н: 465056 Koblitz, Neal
Хэвлэсэн: (1977)

Büchi objectives in countable MDPs
-н: Kiefer, S, зэрэг
Хэвлэсэн: (2019)

Model theory of finite-by-Presburger Abelian groups and finite extensions of $p$-adic fields
-н: Derakhshan, J, зэрэг
Хэвлэсэн: (2016)

Reconstructing D-cap from p-adic Hodge theory
-н: Wiersig, F
Хэвлэсэн: (2024)

Some new directions in p-adic Hodge theory
-н: Kedlaya, Kiran S.
Хэвлэсэн: (2012)

$p$-ADIC HODGE THEORY FOR RIGID-ANALYTIC VARIETIES
-н: PETER SCHOLZE
Хэвлэсэн: (2013-01-01)

Nearly Quadratic Mappings over p-Adic Fields
-н: M. Eshaghi Gordji, зэрэг
Хэвлэсэн: (2012-01-01)

On dynamical systems induced by p-adic number fields
-н: Ilwoo Cho
Хэвлэсэн: (2015-01-01)

Cell decomposition for semiaffine structures on p-adic fields
-н: Eva Leenknegt
Хэвлэсэн: (2012-08-01)

On the decidability of the field of maximal abelian extension of p-adic numbers
-н: Wang, C
Хэвлэсэн: (2018)

The logical strength of Büchi's decidability theorem
-н: Kolodziejczyk, L, зэрэг
Хэвлэсэн: (2019)

The logical strength of Büchi's decidability theorem
-н: Kolodziejczyk, L, зэрэг
Хэвлэсэн: (2016)

Learn with SAT to Minimize Büchi Automata
-н: Stephan Barth, зэрэг
Хэвлэсэн: (2012-10-01)

Construction of p-Adic Gibbs Measure for p-Adic λ-Ising Model
-н: Mutlay Dogan
Хэвлэсэн: (2017-09-01)

Computing p-adic L-functions of totally real fields
-н: Lauder, A, зэрэг
Хэвлэсэн: (2021)

Mirror symmetry and the K theory of a p-adic group
-н: Vaintrob, Dmitry
Хэвлэсэн: (2016)

$p$ -ADIC HODGE THEORY FOR RIGID-ANALYTIC VARIETIES – CORRIGENDUM
-н: PETER SCHOLZE
Хэвлэсэн: (2016-01-01)

Valued fields: p-adic numbers as a case study
-н: Song, Ruiqi
Хэвлэсэн: (2023)

Oxetane Synthesis through the Paternò-Büchi Reaction
-н: Maurizio D'Auria, зэрэг
Хэвлэсэн: (2013-09-01)