scientific article; zbMATH DE number 1512851
The paper is devoted to the study of certain extensions of Presburger arithmetic. Let \(R=(r_{n})\) be a strictly increasing sequence of natural numbers with \(r_{0}=1\). Denote by the same letter the unary predicate \(R(x)\) expressing that \(x\) belongs to the sequence \(R\); let \(S\) be the successor function on \(R\), i.e., \(S(r_{n}) = r_{n+1}\). Two kinds of extensions are considered, namely \(\langle N, +, R \rangle\) and \(\langle N, <, R \rangle\). It is shown, under certain conditions on \(R\), that relative quantifier elimination results hold. It is also shown (a model-theoretic proof is given) that for \(R\) a sparse unary predicate the theory Th\((\langle N, +, R, S \rangle\)) is existential (a syntactic proof was given by A. L. Semenov in 1980). Further, it is discussed under which conditions a sequence \(R\) is (almost) sparse. Finally the theory of \(\langle N, <, R, S \rangle\) is examined. It is proved (by model-theoretic methods) that under certain conditions on \(R\) this theory is existential. For the entire collection see [Zbl 0939.00010].
- On decidable extensions of Presburger arithmetic: from A. Bertrand numeration sytems to Pisot numbers
- scientific article; zbMATH DE number 1512848
- A note on definability in fragments of arithmetic with free unary predicates
- scientific article; zbMATH DE number 4112569
- scientific article; zbMATH DE number 4031630
- Bounding quantification in parametric expansions of Presburger arithmetic
- scientific article; zbMATH DE number 4031630 (Why is no real title available?)
- scientific article; zbMATH DE number 4112569 (Why is no real title available?)
- Presburger arithmetic with unary predicates is Π11 complete
- A generalization of \(p\)-boxes to affine arithmetic
- Deciding Presburger arithmetic by model checking and comparisons with other methods
- On decidable extensions of Presburger arithmetic: from A. Bertrand numeration sytems to Pisot numbers
- A collapse result for extensions of the Presburger arithmetic by a one-place function compatible with addition.
- Expansions of Presburger arithmetic with the exchange property
- Tractable fragments of Presburger arithmetic
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508549)