Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-27T02:28:32.733Z Has data issue: false hasContentIssue false
  • English
  • Français

On decidable extensions of Presburger arithmetic: from A. Bertrand numeration sytems to Pisot numbers

Published online by Cambridge University Press:  12 March 2014

Françoise Point
Françoise Point*
Affiliation:
Senior Research Associate F.N.R.S., Université Mons-Hainaut, 6, Avenue du Champ de Mars, 7, 000 Mons, Belgium E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study extensions of Presburger arithmetic with a unary predicate R and we show that under certain conditions on R, R is sparse (a notion introduced by A. L. Semënov) and the theory of 〈ℕ, +, R〉 is decidable. We axiomatize this theory and we show that in a reasonable language, it admits quantifier elimination. We obtain similar results for the structure 〈ℚ, +, R〉.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 3 , September 2000 , pp. 1347 - 1374
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bateman, P. T., Jockush, C. G., and Woods, A. R., Decidability and undecidability of theories with a predicate for the primes, This Journal , vol. 58 (1993), no. 2, pp. 672–687.Google Scholar
[2]Bertrand-Matms, A., Comment écrire les nombres entiers dans une base qui n' est pas entière, Acta Mathematica Hungarica, vol. 54 (1989), no. 3–4, pp. 237–241.Google Scholar
[3]Bès, A., Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem, This Journal, vol. 62 (1997), no. 4, pp. 1280–1296.Google Scholar
[4]Bruyère, V. and Hansel, G., Bertrand numeration systems and recognizability, Theoretical Computer Science, vol. 181 (1997), pp. 17–43.CrossRefGoogle Scholar
[5]Bruyère, V., Hansel, G., Michaux, C., and Villematre, R., Logic and p-recognizable sets of integers, Bulletin of Belgian Mathematical Society, vol. 1 (1994), pp. 191–238.Google Scholar
[6]Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[7]Chang, C. C. and Keisler, H. J., Model theory, studied in logic and the foundations of mathematics, vol. 73, North-Holland, 1973.Google Scholar
[8]Cherlin, G. and Point, F., On extensions of Presburger arithmetic, Proceedings of the 4th Easter Model Theory Conference (Gross Köris), Humboldt University zu Berlin, 1986, Seminarberichte 86, pp. 17–34.Google Scholar
[9]Delon, F., Q muni de l' arithmétique faible de Penzin est décidable, Proceedings of the American Mathematical Society, vol. 125 (1997), no. 9, pp. 2711–2717.CrossRefGoogle Scholar
[10]Enderton, H. E., An introduction to mathematical logic, Academic Press, New York, 1972.Google Scholar
[11]Frougny, C. and Solomyak, B., On representations of integers in linear numeration systems, Ergodic theory of ℤd-actions (Pollicot, M. and Schmidt, K., editors), London Mathematical Society Lecture Note, vol. 228, 1996, pp. 345–368.Google Scholar
[12]Hodgson, B. R., Décidabilité par automate fini, Les Annales des Sciences Mathématiques du Québec, vol. 7 (1983), pp. 39–57.Google Scholar
[13]Ito, S. and Takahashi, Y., Markov subshifts and realisations of β-expansions, Journal of the Mathematical Society of Japan, vol. 26 (1974), no. 1, pp. 33–55.CrossRefGoogle Scholar
[14]Michaux, C. and Villemaire, R., Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semënov's theorems, Annals of Pure and Applied Logic, vol. 77 (1996), pp. 251–277.CrossRefGoogle Scholar
[15]Parry, W., On the β-expansions of real numbers, Acta Mathematica Hungarica, vol. 11 (1960), pp. 401–416.Google Scholar
[16]Penzin, Yu., Solvability of the theory of integers with addition, order, and multiplication by an arbitrary number, Mathematical Notes, (1973), pp. 401–405, translation of Matematicheskie Zametki, vol. 13, no. 5, pp. 667–675, 1973.Google Scholar
[17]Point, F. and Bruyère, V., On the Cobham-Semënov Theorem, Theory of Computing Systems, vol. 30 (1997), pp. 197–220.Google Scholar
[18]Robinson, J., Definability and decision problems in arithmetic, This Journal, vol. 14 (1949), no. 2, pp. 98–114.Google Scholar
[19]Semënov, A. L., On certain extension of the arithmetic of addition of natural numbers. Mathematics of the USSR-hvestiya, vol. 15 (1980), no. 2, pp. 401–418.Google Scholar
[20]Semënov, A. L., Logical theories of one-place functions on the set of natural numbers, Mathematics of the USSR-hvestiya, vol. 22 (1984), no. 3, pp. 587–618.Google Scholar
[21]Shallit, J., Numeration systems, linear recurrences, and regular sets, I. C. A. L. P. 92 (Wien), Lecture Notes in Computer Science, no. 623, 1992, pp. 89–100.Google Scholar
[22]Solomyak, B., Conjugates of beta-numbers and the zero-free for a class of analytic functions. Proceedings of the London Mathematical Society, vol. 68 (1994), pp. 477–498.Google Scholar
[23]van den Dries, L., The field of reals with a predicate for powers of two, Manuscripta Mathematica, vol. 54 (1985), pp. 187–195.CrossRefGoogle Scholar
[24]Villemaire, R., The theory of 〈ℕ, +, Vk, V1〉 is undecidable, Theoretical Computer Science, vol. 106 (1992), pp. 337–349.CrossRefGoogle Scholar