On the images of N-rational sequences counting multiplicities

: Honkala J, Ruohonen K

Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD

: 2003

: International Journal of Algebra and Computation

: INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION

: INT J ALGEBR COMPUT

: 13

: 3

: 303

: 321

: 19

: 0218-1967

DOI: https://doi.org/10.1142/S0218196703001390

A mapping phi : Z --> Z is called piecewise affine if there exist integers a greater than or equal to 1 and u(j) greater than or equal to 1, v(j) for 0 less than or equal to j < a such that phi(an + j) = u(j)n + v(j) whenever n is an element of Z and 0 less than or equal to j < a. We prove that if s = (s(n))(n)greater than or equal too and t = (t(n))(n)greater than or equal to0 are N-rational sequences such that s takes each value exactly as many times as t, then there exists a piecewise affine mapping phi: Z --> Z such that s(n) = t(phi(n)) for almost all n greater than or equal to 0. As an application we solve the HDOL language equivalence problem in some cases.