Approximate comparison of distance automata

Prelegent(ci)

Laure Daviaud

Afiliacja

LIAFA, Université Paris 7

Termin

12 czerwca 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Thomas Colcombet

Seminarium

Seminarium „Teoria automatów”

---

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.

---