Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Defining multiplication in some additive expansions of polynomial rings ; Rigo, Michel ; in Communications in Algebra (2016), 44 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 20 (7 ULg)Defining multiplication for polynomials over a finite field. Rigo, Michel ; E-print/Working paper (2011) Let $P$ and $Q$ be two non-zero multiplicatively independent polynomials with coefficients in a finite field $\mathbb{F}$. Adapting a result of R.~Villemaire, we show that multiplication of polynomials is ... [more ▼] Let $P$ and $Q$ be two non-zero multiplicatively independent polynomials with coefficients in a finite field $\mathbb{F}$. Adapting a result of R.~Villemaire, we show that multiplication of polynomials is a ternary relation $\{(A,B,C)\in\mathbb{F}[X]\mid A.B=C\}$ definable by a first-order formula in a suitable structure containing both functions $V_P$ and $V_Q$ where $V_A(B)$ is defined as the greatest power of $A$ dividing $B$. Such a result has to be considered in the context of a possible analogue of Cobham's theorem for sets of polynomials whose $P$-expansions are recognized by some finite automaton. [less ▲] Detailed reference viewed: 95 (6 ULg)Logical characterization of recognizable sets of polynomials over a finite field Rigo, Michel ; in International Journal of Foundations of Computer Science (2011), 22(7), 1549-1563 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 123 (14 ULg) |
||