un)decidabilit

Speaker(s)

Laure Laviaud

Affiliation

Uniwersytet Warszawski

Date

Oct. 12, 2016, 2:15 p.m.

Room

room 5870

Title in Polish

About max-plus and min-plus automata:

Seminar

Seminar Automata Theory

---

In this talk, I will present min-plus and max-plus automata, which are a kind of weighted automata computing functions from the set of words to the integers. I will give some classical results about decision problems (equivalence, comparison, determinisation) and - most important - I will give a lot of remaining open problems on the subject.
Depending on time, I will try to give general ideas of how to address these problems via the matrix representation of weighted automata.

---