文章基本信息

标题：Approximate comparison of distance automata
本地全文：下载
作者：Thomas Colcombet ; Laure Daviaud
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：20
页码：574-585
DOI：10.4230/LIPIcs.STACS.2013.574
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Distance automata are automata weighted over the semiring (\mathbb{N} \cup \infty,\min,+) (the tropical semiring). Such automata compute functions from words to \mathbb{N} \cup \infty such as the number of occurrences of a given letter. It is known that testing f 0 and two functions f,g computed by distance automata, answers "yes" if f <= (1-epsilon) 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.
关键词：Distance automata; tropical semiring; decidability; cost functions