joint work with Thomas Colcombet

Speaker(s)

Laure Daviaud

Affiliation

LIAFA, Université Paris 7

Date

June 12, 2013, 2:15 p.m.

Room

room 5870

Title in Polish

Approximate comparison of distance automata

Seminar

Seminar Automata Theory

---

Distance automata are automata weighted over the semiring (N U {+infinity},min,+) (the tropical semiring).
Such automata compute functions from words to N U {+infinity} such as the number of occurrences of a given letter.
It is known that testing f I will give an approximation of this problem  that is decidable.

I will present an algorithm which, given e>0 and two functions f,g computed by distance automata, answers ``yes'' if f(1+e)g(w), and may answer ``yes'' or ``no'' in all other cases. This result highly refines previously known decidability results of the same type.

The core argument behind this quasi-decision procedure is an algorithm which is able to provide an approximated finite presentation to the closure under products of sets of matrices over the tropical semiring.

I will also give another theorem, of affine domination, which shows that previously known decision procedures for cost-automata have an improved precision when used over distance automata.

---