You are not logged in |
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
- 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.
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.
