License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.66
URN: urn:nbn:de:0030-drops-33517
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3351/
Go to the corresponding LIPIcs Volume Portal

Kuperberg, Denis ; Vanden Boom, Michael

Quasi-Weak Cost Automata: A New Variant of Weakness

pdf-format:
33.pdf (0.4 MB)

Abstract

Cost automata have a finite set of counters which can be manipulated on each transition but do not affect control flow. Based on the evolution of the counter values, these automata define functions from a domain like words or trees to \N \cup \set{\infty}, modulo an equivalence relation which ignores exact values but preserves boundedness properties. These automata have been studied by Colcombet et al. as part of a "theory of regular cost functions", an extension of the theory of regular languages which retains robust equivalences, closure properties, and decidability like the classical theory.

We extend this theory by introducing quasi-weak cost automata. Unlike traditional weak automata which have a hard-coded bound on the number of alternations between accepting and rejecting states, quasi-weak automata bound the alternations using the counter values (which can vary across runs). We show that these automata are strictly more expressive than weak cost automata over infinite trees. The main result is a Rabin-style characterization theorem: a function is quasi-weak definable if and only if it is definable using two dual forms of non-deterministic Büchi cost automata. This yields a new decidability result for cost functions over infinite trees.

BibTeX - Entry

@InProceedings{kuperberg_et_al:LIPIcs:2011:3351,
  author =	{Denis Kuperberg and Michael Vanden Boom},
  title =	{{Quasi-Weak Cost Automata: A New Variant of Weakness }},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{66--77},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3351},
  URN =		{urn:nbn:de:0030-drops-33517},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.66},
  annote =	{Keywords: Automata, infinite trees, cost functions, weak}
}

Keywords: Automata, infinite trees, cost functions, weak
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

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