Kuperberg, Denis ;
Vanden Boom, Michael
QuasiWeak Cost Automata: A New Variant of Weakness
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 quasiweak cost automata. Unlike traditional weak automata which have a hardcoded bound on the number of alternations between accepting and rejecting states, quasiweak 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 Rabinstyle characterization theorem: a function is quasiweak definable if and only if it is definable using two dual forms of nondeterministic 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 = {{QuasiWeak Cost Automata: A New Variant of Weakness }},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {6677},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3351},
URN = {urn:nbn:de:0030drops33517},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.66},
annote = {Keywords: Automata, infinite trees, cost functions, weak}
}
Keywords: 

Automata, infinite trees, cost functions, weak 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Issue date: 

2011 
Date of publication: 

2011 