Defining multiplication in some additive expansions of polynomial rings

[en] Adapting a result of R. Villemaire on expansions of Presburger arithmetic, we show how to define multiplication in some expansions of the additive reduct of certain Euclidean rings. In particular, this applies to polynomial rings over a finite field.

Disciplines :

Mathematics

Author, co-author :

Point, Françoise

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Waxweiler, Laurent

Language :

English

Title :

Defining multiplication in some additive expansions of polynomial rings

Publication date :

2016

Journal title :

Communications in Algebra

ISSN :

0092-7872

eISSN :

1532-4125

Publisher :

Taylor & Francis Ltd

Volume :

Pages :

2075-2099

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 26 February 2015

Statistics

Number of views

84 (18 by ULiège)

Number of downloads

2 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

S.Akiyama, Petho A. (2002). On canonical number systems. Theoret. Comput. Sci. 270(1–2): 921–933.
A.Bès, (1997). Undecidable extensions of Büchi arithmetic and Cobham-Semënov theorem. Journal of Symb. Logic 62(4):1280–1296.
V.Bruyère,, G.Hansel,, C.Michaux,, R.Villemaire, (1994). Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1:191–238.
J.R.Büchi, (1960). Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlag. Math. 6:66–92.
A.Cobham, (1969). On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3:186–192.
L.van den Dries, (1985). The field of reals with a predicate for powers of two. Manuscripta Mathematica 54:187–195.
L.van den Dries, (1985). On expansions of ℚ and ℤ (Manuscript).
F.Durand,, M.Rigo, On Cobham's theorem. To appear in Handbook of Automata: from Mathematics to Applications, European Math. Society Publishing house.
C.C.Elgot,, M.O.Rabin, (1966). Decidability and undecidability of extensions of second (first order theory of generalized) successor. Journal of Symbolic Logic 31(2):169–181.
P.Eklof,, E.Fischer, (1972). The elementary theory of abelian groups. Ann. Math. Logic 4:115–171.
H.B.Enderton, (1972). A Mathematical Introduction to Logic. New York, London: Academic Press.
W.Hodges, (1993). Model Theory, Encyclopedia of Mathematics and its applications 42, Cambridge: Cambridge University Press.
B.R.Hodgson, (1976). Théories décidables par automate fini, Ph.D. Thesis, Université de Montréal.
N.Jacobson, (1985). Basic Algebra 1, W.H. Freeman and Compagny, San Francisco (second edition).
B.Kovács, Petho, A. (1991). Number systems in integral domains, especially in orders of algebraic number fields. Acta Sci. Math. 55:287–299.
M.M.Madritsch, (2012). The sum-of-digits function of canonical number systems: Distribution in residue classes. Journal of Number Theory 132:2756–2772.
R.McNaughton, (1963). Review. Journal Symbolic Logic 29(1):100–102.
C.Michaux,, R.Villemaire, (1996). 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:251–277.
A.A.Muchnik, An. A. (2003). The definable criterion for definability in Presburger arithmetic and its applications. Theoret. Comput. Sci. 290:1433–1444.
A.Nies, (2007). Describing groups. Bull. Symbolic Logic 13(3):305–339.
A.Nies,, R.M.Thomas, (2008). FA-presentable groups and rings. J. Algebra 320(2):569–585.
J.G.Penzin, Ju. G. (1973). Decidability of the theory of integers with addition, order and multiplication by an arbitrary number. Mat. Zametki 13:667–675.
F.Point, (2000). On decidable extensions of Presburger arithmetic: from A. Bertrand numeration systems to Pisot numbers. Journal of Symbolic Logic 65(3):1347–1374.
M.Presburger, (1929). Über die Vollstä ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt in Comptes Rendus du I congrès de Mathématiciens des Pays Slaves. Warszawa: 92-101, translated from the german and with commentaries by Dale Jacquette, On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation, Hist. Philos. Logic12 (1991), no. 2, 225–233.
M.Rigo, (2008). Syntactical and automatic properties of sets of polynomials over finite fields. Finite Fields Appl. 14:258–276.
M.Rigo,, L.Waxweiler, (2011). Logical characterization of recognizable sets of polynomials over a finite field. Int. J. Found. Comput. Sci. 22:1549–1563.
R.M.Robinson, (1951). Undecidable rings. Trans. Amer. Math. Soc. 70:137–159.
P.Samuel, (1971). About euclidean rings. Journal of Algebra 19:282–301.
A.L.Semënov, (1977). The Presburger nature of predicates that are regular in two number systems Sibirsk. Mat. Ž. 18:403–418.
A.Sirokofskich, (2010). On an exponential predicate in polynomials over finite fields. Proc. Amer. Math. Soc. 138:2569–2583.
A.Sirokofskich, (2012). Decidability questions for a ring of Laurent polynomials. Ann. Pure Appl. Logic 163(5):615–619.
W.Szmielew, (1955). Elementary properties of Abelian groups. Fund. Math. 41:203–271.
W.Thomas, (1975). A note on undecidable extensions of monadic second order successor arithmetic. Arch. Math. Logik 17:43–44.
R.Villemaire, (1992). The theory of ⟨ N, +, Vk, Vl ⟩ is undecidable. Theoret. Comput. Sci. 106(2):337–349.
R.Villemaire, (1992). Joining k- and l-recognizable sets of natural numbers, STACS 92 (Cachan, 1992), 83–94, Lecture Notes in Comput. Sci 577, Berlin: Springer.
L.Waxweiler, (2009). Caractère reconnaissable d'ensembles de polynômes à coefficients dans un corps fini, Ph. D. thesis, University of Liège, Available from http://orbi.ulg.ac.be/handle/2268/11381 (last accessed 1st December 2014).