City Research Online

Approximate Comparison of Functions Computed by Distance Automata

Colcombet, T. and Daviaud, L. (2016). Approximate Comparison of Functions Computed by Distance Automata. Theory of Computing Systems, 58(4), pp. 579-613. doi: 10.1007/s00224-015-9643-3

Abstract

Distance automata are automata weighted over the semiring (N∪{∞},min,+) (the tropical semiring). Such automata compute functions from words to N∪{∞}. 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.

Publication Type: Article
Additional Information: This is a post-peer-review, pre-copyedit version of an article published in 'Theory of Computing Systems'. The final authenticated version is available online at: https://doi.org/10.1007/s00224-015-9643-3.
Publisher Keywords: Distance automata, Asymptotic behaviour, Weighted automata, Tropical semiring, Comparison
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
URI: http://openaccess.city.ac.uk/id/eprint/21296
[img]
Preview
Text - Accepted Version
Download (516kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login