TY - GEN

T1 - Approximate comparison of distance automata

AU - Colcombet, Thomas

AU - Daviaud, Laure

PY - 2013

Y1 - 2013

N2 - Distance automata are automata weighted over the semiring (N [ {∞}, min, +) (the tropical semiring). Such automata compute functions from words to N [ {∞} such as the number of occurrences of a given letter. It is known that testing f 6 g is an undecidable problem for f, g computed by distance automata. The main contribution of this paper is to show that an approximation of this problem becomes decidable. We present an algorithm which, given ≤ 0 and two functions f, g computed by distance automata, answers yes if f 6 (1-ε)g, no if f ≰ g, 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. We also provide another theorem, of affine domination, which shows that previously known decision procedures for cost-automata have an improved precision when used over distance automata.

AB - Distance automata are automata weighted over the semiring (N [ {∞}, min, +) (the tropical semiring). Such automata compute functions from words to N [ {∞} such as the number of occurrences of a given letter. It is known that testing f 6 g is an undecidable problem for f, g computed by distance automata. The main contribution of this paper is to show that an approximation of this problem becomes decidable. We present an algorithm which, given ≤ 0 and two functions f, g computed by distance automata, answers yes if f 6 (1-ε)g, no if f ≰ g, 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. We also provide another theorem, of affine domination, which shows that previously known decision procedures for cost-automata have an improved precision when used over distance automata.

KW - Cost functions

KW - Decidability

KW - Distance automata

KW - Tropical semiring

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

U2 - 10.4230/LIPIcs.STACS.2013.574

DO - 10.4230/LIPIcs.STACS.2013.574

M3 - Conference contribution

AN - SCOPUS:84892598678

SN - 9783939897507

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 574

EP - 585

BT - 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013

T2 - 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013

Y2 - 27 February 2013 through 2 March 2013

ER -