City Research Online

Approximate comparison of distance automata

Colcombet, T. and Daviaud, L. (2013). Approximate comparison of distance automata. In: Portier, N. and Wilke, T. (Eds.), 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), 20. (pp. 574-585). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. ISBN 9783939897507


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 <= 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 <= (1-ε ) g, "no" if f \not\leq 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.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © Thomas Colcombet and Laure Daviaud; licensed under Creative Commons License BY-ND
Publisher Keywords: Distance automata, tropical semiring, decidability, cost functions
Subjects: Q Science > QA Mathematics
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
Date available in CRO: 21 Jan 2019 13:59
Date deposited: 21 January 2019
Date of first online publication: 2013
Text - Published Version
Available under License Creative Commons Attribution No Derivatives.

Download (643kB) | Preview



Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login