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

書目詳細資料
Main Authors:	Guépin, F, Haase, C, Worrell, J
格式:	Conference item
出版:	IEEE 2019

相似書籍

On the expressiveness of Büchi arithmetic
由: Haase, C, et al.
出版: (2021)

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

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

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

Markov chains and unambiguous Büchi automata
由: Baier, C, et al.
出版: (2016)

Markov Chains and Unambiguous Büchi Automata
由: Kiefer, S, et al.
出版: (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, et al.
出版: (2023)

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

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

Parallel Implementation of Exact Matrix Computation Using Multiple P-adic Arithmetic
由: Xinkai Li, et al.
出版: (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, et al.
出版: (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, et al.
出版: (2019)

Model theory of finite-by-Presburger Abelian groups and finite extensions of $p$-adic fields
由: Derakhshan, J, et al.
出版: (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, et al.
出版: (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, et al.
出版: (2019)

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

Learn with SAT to Minimize Büchi Automata
由: Stephan Barth, et al.
出版: (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, et al.
出版: (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, et al.
出版: (2013-09-01)