[en] The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P playing the role of the base of the numeration. Having in mind the theorem of Cobham from 1969 about recognizable sets of integers, it is natural to study $P$-recognizable sets of polynomials. Based on the results obtained in the Ph.D. thesis of the second author, we study the logical characterization of such sets and related properties like decidability of the corresponding first-order theory.
Disciplines :
Mathematics Computer science
Author, co-author :
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Waxweiler, Laurent
Language :
English
Title :
Logical characterization of recognizable sets of polynomials over a finite field
Publication date :
2011
Journal title :
International Journal of Foundations of Computer Science
ISSN :
0129-0541
Publisher :
World Scientific Publishing Company
Special issue title :
Special issue of DLT 2010
Volume :
22
Issue :
7
Pages :
1549-1563
Peer reviewed :
Peer Reviewed verified by ORBi
Commentary :
Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P seen as a base of numeration. We study P-recognizable sets of polynomials, i.e., sets whose language of representations in base P is regular, their logical characterization and related properties like decidability of the corresponding first-order theory.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
J.-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge University Press, 2003.
E. Bach, J. Shallit, Algorithmic number theory, Vol. 1., Efficient algorithms. Foundations of Computing Series, MIT Press, 1996.
V. Berthé, M. Rigo, eds, Combinatorics, Automata and Number Theory, Encyclopedia of Mathematics and its Applications 135, Cambridge University Press, 2010.
A. Bès, A survey of arithmetical definability, Bull. Belg. Math. Soc. Simon Stevin (2001), suppl., 1-54.
V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994), 191-238.
J. R. Büchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grun- lag. Math. 6 (1960), 66-92.
A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969), 186-192.
S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press (1974).
H. E. Enderton, An introduction to mathematical logic, Academic Press (1972).
G. Hansel, Systèmes de numération indépendants et syndéticité, Theoret. Comput. Sci. 204 (1998), 119-130.
C. Michaux, R. Villemaire, Presburger arithmetic and recognizability of sets of natural numbers by automata: new proofs of Cobham's and Semenov's theorems, Ann. Pure Appl. Logic 77 (1996), 251-277.
M. Minsky, S. Papert, Unrecognizable sets of numbers, J. Assoc. Comput. Mach. 13 (1966), 281-286.
T. Pheidas, K. Zahidi, Elimination theory for addition and the Frobenius map in polynomial rings, J. Symbolic Logic 69 (2004), 1006-1026.
M. Presburger, Über die volständigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortritt, C. R. Premier congrès des Mathématiciens des pays slaves, Varsovie, pages 92-101, 1929.
N. Rampersad, personal communication, October 2010.
M. Rigo, Syntactical and automatic properties of sets of polynomials over finite fields, Finite Fields Appl. 14 (2008), 258-276.
M. Rigo, Numeration Systems: a Link between Number Theory and Formal Language Theory, Proceedings of Developments in Language Theory, London, Ontario, Canada, Lect. Notes in Comput. Sci. 6224, 33-53 Springer-Verlag (2010).
M. Rigo, L. Waxweiler, A note on syndeticity, recognizable sets and Cobham's theorem, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 88 (2006), 169-173.
A. Sirokofskich, Decidability of Sub-theories of Polynomials over a Finite Field, Mathematical Theory and Computational Practice, Lect. Notes in Comput. Sci. 5635, 437-446 Springer (2009).
A. Sirokofskich, On an exponential predicate in polynomials over finite fields, Proc. Amer. Math. Soc. 138 (2010), 2569-2583.
L. Waxweiler, Caractère reconnaissable d'ensembles de polyno̧mes à coeffi- cients dans un corps fini, Ph. D. thesis, University of Liège, December 2009, http://orbi.ulg.ac.be/handle/2268/ 11381
R. Villemaire, The theory of (N,+, Vk, Vl) is undecidable, Theoret. Comput. Sci. 106 (1992), 337-349.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
