TY - JOUR

T1 - Approximate comparison of functions computed by distance automata

AU - Colcombet, Thomas

AU - Daviaud, Laure

N1 - Funding Information: The research leading to these results has received funding from the European Union’s Seventh Framework Programme (FP7/2007-2013) under grant agreement n 259454, and from the project ANR 2010 BLAN 0202 02 FREC.

PY - 2016/5/1

Y1 - 2016/5/1

N2 - Distance automata are automata weighted over the semiring (Formula presented.) (the tropical semiring). Such automata compute functions from words to (Formula presented.). It is known from Krob that the problems of deciding ‘ f≤g’ or ‘ f=g’ for f and g computed by distance automata is an undecidable problem. The main contribution of this paper is to show that an approximation of this problem is decidable. We present an algorithm which, given ε>0 and two functions f,g computed by distance automata, answers “yes” if f≤(1−ε)g, “no” if f≦̸g, and may answer “yes” or “no” in all other cases. The core argument behind this quasi-decision procedure is an algorithm which is able to provide an approximated finite presentation of the closure under products of sets of matrices over the tropical semiring. Lastly, our theorem of affine domination gives better bounds on the precision of known decision procedures for cost automata, when restricted to distance automata.

AB - Distance automata are automata weighted over the semiring (Formula presented.) (the tropical semiring). Such automata compute functions from words to (Formula presented.). It is known from Krob that the problems of deciding ‘ f≤g’ or ‘ f=g’ for f and g computed by distance automata is an undecidable problem. The main contribution of this paper is to show that an approximation of this problem is decidable. We present an algorithm which, given ε>0 and two functions f,g computed by distance automata, answers “yes” if f≤(1−ε)g, “no” if f≦̸g, and may answer “yes” or “no” in all other cases. The core argument behind this quasi-decision procedure is an algorithm which is able to provide an approximated finite presentation of the closure under products of sets of matrices over the tropical semiring. Lastly, our theorem of affine domination gives better bounds on the precision of known decision procedures for cost automata, when restricted to distance automata.

KW - Asymptotic behaviour

KW - Comparison

KW - Distance automata

KW - Tropical semiring

KW - Weighted automata

UR - http://www.scopus.com/inward/record.url?scp=84962642640&partnerID=8YFLogxK

U2 - 10.1007/s00224-015-9643-3

DO - 10.1007/s00224-015-9643-3

M3 - Article

AN - SCOPUS:84962642640

VL - 58

SP - 579

EP - 613

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -