Logical characterization of recognizable sets of polynomials over a finite field

Rigo, Michel; Waxweiler, Laurent

doi:10.1142/S0129054111008878

Request a copy

Article (Scientific journals)

Logical characterization of recognizable sets of polynomials over a finite field

Rigo, Michel; Waxweiler, Laurent

2011 • In International Journal of Foundations of Computer Science, 22 (7), p. 1549-1563

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/87301

DOI
10.1142/S0129054111008878

Files (1)Send to Details Statistics Bibliography Similar publications

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

RIS BibTex APA Chicago Permalink X Linkedin

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 :

Issue :

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

240 (45 by ULiège)

Number of downloads

16 (14 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

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.