Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-22T23:01:44.155Z Has data issue: false hasContentIssue false
  • English
  • Français

An extension of the Cobham-Semënov Theorem

Published online by Cambridge University Press:  12 March 2014

Alexis Bès
Alexis Bès*
Affiliation:
Llaic 1 and Team of Mathematical Logic, Paris 7, France
*
Correspondence address: Equipe de Logique Mathématique UPRESA 7048, Université Paris7, 2 place Jussieu, 75251 Paris Cedex 05, France, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Let θ, θ′ be two multiplicatively independent Pisot numbers, and let U, U′ be two linear numeration systems whose characteristic polynomial is the minimal polynomial of θ and θ′, respectively. For every n ≥ 1, if A ⊆ ℕn is U-and U′ -recognizable then A is definable in 〈ℕ: + 〉.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 1 , March 2000 , pp. 201 - 211
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]Bès, A., Undecidable extensions of Büchi arithmetic and Cobham-Sèmenov theorem, this Journal, vol. 62 (1997), no. 4, pp. 1280–1296.Google Scholar
[2]Bruyère, V., Entiers et automates finis, U.E. Mons, mémoire de licence, 1984–1985.Google Scholar
[3]Bruyère, V. and Hansel, G., Bertrand numeration systems and recognizability, Theoretical Computer Science, vol. 181 (1997), pp. 17–43.CrossRefGoogle Scholar
[4]Bruyère, V., Hansel, G., Michaux, C., and Villemaire, R., Logic and p-recognizable sets of integers, Bulletin of Belgian Mathematical Society, vol. 1 (1994), pp. 191–238.Google Scholar
[5]Büchi, J.R., Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logic und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[6]Cobham, A., On the base-dependance of sets of numbers recognizable by finite automata, Mathematical Systems Theory, vol. 3 (1969), pp. 186–192.CrossRefGoogle Scholar
[7]Durand, F., A generalization of Cobham's theorem, Theory of Computing Systems, vol. 31 (1998), pp. 169–185.CrossRefGoogle Scholar
[8]Fabre, S., Une généralisation du théorème de Cobham, Acta Arithmetica, vol. 67 (1994), pp. 197–208.CrossRefGoogle Scholar
[9]Fagnot, I., Cobham's theorem and automaticity in non-standard bases, preprint, Paris 7 University, 1998.Google Scholar
[10]Fraenkel, A.S., Systems of numeration, American Mathematical Monthly, vol. 92 (1985), pp. 105–114.CrossRefGoogle Scholar
[11]Frougny, C. and Solomyak, B., On representation of integers in linear numeration systems, Ergodic theory of ℤd actions. Proceedings of the Warwick symposium, Warwick, UK, 1993–94 (Pollicott, Market al., editors), London Mathematical Society Lecture Note Series, vol. 228, New York: Cambridge University Press, 1996, pp. 345–368.Google Scholar
[12]Hansel, G., A propos d'un théorème de Cobham, Actes de la Fete des Mots, Greco de Programmation, CNRS, Rouen, France (Perrin, D., editor), 1992.Google Scholar
[13]Hansel, G., Systèmes de numération indépendants et syndéticité, Theoretical Computer Science, vol. 204, No. 1–2 (1998), pp. 119–130.CrossRefGoogle Scholar
[14]Michaux, C. and Villemaire, R., Cobham's theorem seen through Büchi theorem, Proceedings of Icalp'93, Springer Lecture Notes in Computer Science, vol. 700, 1993, pp. 325–334.Google Scholar
[15]Michaux, C., Open questions around Buchi and Presburger arithmetics, Logic: From foundations to applications, Proceedings of the European Logic Colloquium '93, Oxford University Press, 1996, pp. 353–383.CrossRefGoogle Scholar
[16]Michaux, C., Presburger arithmetic and recognizability of sets of natural numbers by automata: new proofs of Cobham's and Semenov's theorems, Annals of Pure and Applied Logic, vol. 77 (1996), pp. 251–277.CrossRefGoogle Scholar
[17]Muchnik, A., Definable criterion for definability in Presburger Arithmetic and its application, (in Russian), preprint, Institute of new technologies, 1991.Google Scholar
[18]Point, F. and Bruyère, V., On the Cobham-Semenov theorem, Theory of Computing Systems, vol. 30 (1997), pp. 197–220.Google Scholar
[19]Semenov, A. L., The Presburger nature of predicates that are regular in two number systems, Siberian Mathematical Journal, vol. 18 (1977), pp. 289–299.CrossRefGoogle Scholar