scientific article; zbMATH DE number 1512848
The mutual isolation in which the two main political blocks of the world lived during most of the second half of the 20th century led in the former Soviet Union to the production of scientific work which in the Western world didn't get the attention that it deserved. Even though much of this work has been translated into English, the lack of personal contact made many of these results mostly unknown in the West. This paper is an attempt to stimulate interest for and to make better known the main results of \textit{A. L. Semenov}'s paper ``On certain extensions of the arithmetic of addition of natural numbers [Math. USSR, Izv. 15, 401-418 (1980; Zbl 0443.03008), English translation of Izv. Akad. Nauk SSSR, Ser. Mat. 43, 1175-1195 (1979; Zbl 0417.03005)]. Semenov worked extensively on definability and decidability of fragments of arithmetic. It is this reviewer's opinion that unfortunately Semenov's work didn't get the attention that it deserved, hence this paper is a welcome contribution. A. Maes gives in the reviewed paper a very readable and carefully written exposition of some of Semenov's results [loc. cit.]. He gives an approach different to Semenov's original exposition and also gives complete proofs. The most important results are 1) a necessary and sufficient condition for the theory of \(\langle\omega;S,<,0,P\rangle\) to admit quantifier elimination for \(\omega\), the naturals, \(S\), the successor function, and \(P\), a set of unary predicates, and 2) a necessary and sufficient condition for the decidability of \(\langle\omega;+,R\rangle\) for a unary predicate \(R\) belonging to a particular class (the sparse predicates). Finally the paper ends with some well explained examples illustrating the theorems. For the entire collection see [Zbl 0939.00010].
- scientific article; zbMATH DE number 1827828
- Fragments of arithmetic and pairing functions
- Decision procedures for elementary sublanguages of set theory. XV: Multilevel syllogistic extended by the predicate Finite and the operators singleton and \(pred_ <\)
- scientific article; zbMATH DE number 51556
- scientific article; zbMATH DE number 4181317
- scientific article; zbMATH DE number 440479
- Kripke, Belnap, Urquhart and relevant decidability \(\&\) complexity. ``Das ist nicht Mathematik. Das ist Theologie
- Decision algorithms for some fragments of analysis and related areas
- Pure Logic with Branched Quantifiers
- Finite automata, real time processes and counting problems in bounded arithmetics
- Morphisms and almost-periodicity
- Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
- scientific article; zbMATH DE number 4031630 (Why is no real title available?)
- On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
- scientific article; zbMATH DE number 1512851 (Why is no real title available?)
- 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.
- An introduction to the theory of linear integer arithmetic (invited paper)
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 Q4508546)