Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-05T22:28:06.352Z Has data issue: false hasContentIssue false

On Sequences Defined by D0L Power Series

Published online by Cambridge University Press:  15 August 2002

Juha Honkala*
Affiliation:
Department of Mathematics, University of Turku, FIN-20014 Turku, Finland, and Turku Centre for Computer Science TUCS, FIN-20520 Turku, Finland; [email protected].
Get access

Abstract

We study D0L power series over commutative semirings. We show that a sequence(cn )n≥0 of nonzero elements of a field A is the coefficientsequence of a D0L power series if and only if there exist a positive integerk and integers βi for 1 ≤ ik such that $c_{n+k}=c_{n+k-1}^{\beta_1}c_{n+k-2}^{\beta_2}\ldots c_n^{\beta_k}$ for alln ≥ 0. As a consequence we solve the equivalence problem of D0L powerseries over computable fields.

Type
Research Article
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer, Berlin (1988).
J. Honkala, On morphically generated formal power series. RAIRO, Theoret. Informatics Appl. 29 (1995) 105-127.
Honkala, J., On the decidability of some equivalence problems for L algebraic series. Intern. J. Algebra and Comput. 7 (1997) 339-351. CrossRef
J. Honkala, On D0L power series, Theoret. Comput. Sci., to appear.
W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer, Berlin (1986).
G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980).
G. Rozenberg and A. Salomaa, Eds., Handbook of Formal Languages 1-3 . Springer, Berlin (1997).
A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer, Berlin (1978).