or: power series in a single variable

Speaker(s)

Joost Winter

Affiliation

Uniwersytet Warszawski

Date

Jan. 11, 2017, 2:15 p.m.

Room

room 5870

Title in Polish

Decidability of equivalence of algebraic streams

Seminar

Seminar Automata Theory

---

In this talk, I will show the decidability of equivalence of algebraic streams (or, equivalentnly, power series in a single variable) over commutative rings that are, in some sense "computable". This result is a partial generalization of earlier results by Salomaa/Soittola 1978 (where it is proven for N), Kuich/Salomaa 1986 (where it is proven for Q), and of Honkala 1996 (where it is proven for computable fields). The proof technique used, however, is rather different, essentially relying on Hilbert's basis theorem and the characterization of algebraic power series given in Wechler 1983.

If time allows, I will also talk about the connections of this result to the coalgebraic method, in particular to bisimulation up-to techniques.

---