Decidability of equivalence of algebraic streams

Prelegent(ci)

Joost Winter

Afiliacja

Uniwersytet Warszawski

Termin

11 stycznia 2017 14:15

Pokój

p. 5870

Tytuł w języku angielskim

or: power series in a single variable

Seminarium

Seminarium „Teoria automatów”

---

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.

---