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.
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 present an algorithm which, given e>0 and two functions f,g computed by distance automata, answers ``yes'' if f
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.