Nie jesteś zalogowany | Zaloguj się

Approximate comparison of distance automata

Prelegent(ci)
Laure Daviaud
Afiliacja
LIAFA, Université Paris 7
Termin
12 czerwca 2013 14:15
Pokój
p. 5870
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.