License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.574
URN: urn:nbn:de:0030-drops-39667
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3966/
Go to the corresponding LIPIcs Volume Portal

Colcombet, Thomas ; Daviaud, Laure

Approximate comparison of distance automata

pdf-format:
54.pdf (0.6 MB)

Abstract

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 <= 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 epsilon > 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.

BibTeX - Entry

@InProceedings{colcombet_et_al:LIPIcs:2013:3966,
  author =	{Thomas Colcombet and Laure Daviaud},
  title =	{{Approximate comparison of distance automata}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{574--585},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3966},
  URN =		{urn:nbn:de:0030-drops-39667},
  doi =		{10.4230/LIPIcs.STACS.2013.574},
  annote =	{Keywords: Distance automata, tropical semiring, decidability, cost functions}
}

Keywords: Distance automata, tropical semiring, decidability, cost functions
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI