On Algebraicness of D0L Power Series

Juha Honkala (Department of Mathematics University of Turku and Turku Centre for Computer Science (TUCS), Finland)

Abstract: We show that it is decidable whether or not a given D0L power series over a semiring A is A-algebraic in case A = Q+ or A = N. The proof relies heavily on the use of elementary morphisms in a power series framework and gives also a new method to decide whether or not a given D0L language is context-free.

Categories: F.4.3