Reference : Logical characterization of recognizable sets of polynomials over a finite field
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/87301
Logical characterization of recognizable sets of polynomials over a finite field
English
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Waxweiler, Laurent [> >]
2011
International Journal of Foundations of Computer Science
World Scientific Publishing Company
22
7
Special issue of DLT 2010
1549-1563
Yes (verified by ORBi)
International
0129-0541
[en] Numeration System ; Finite field ; Polynomial ; Presburger arithmetic ; Logical characterization ; Decidable theory
[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.
Researchers
http://hdl.handle.net/2268/87301
10.1142/S0129054111008878
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.

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
polylogic.pdfAuthor preprint215 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.