Article (Scientific journals)
Logical characterization of recognizable sets of polynomials over a finite field
Rigo, Michel; Waxweiler, Laurent
2011In International Journal of Foundations of Computer Science, 22 (7), p. 1549-1563
Peer Reviewed verified by ORBi
 

Files


Full Text
polylogic.pdf
Author preprint (220.16 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Numeration System; Finite field; Polynomial; Presburger arithmetic; Logical characterization; Decidable theory
Abstract :
[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.
Available on ORBi :
since 18 March 2011

Statistics


Number of views
217 (45 by ULiège)
Number of downloads
15 (14 by ULiège)

Scopus citations®
 
3
Scopus citations®
without self-citations
2
OpenCitations
 
3

Bibliography


Similar publications



Contact ORBi