The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Wojciech Krzysztof Czerwinski, Engel Lefaucheux, Filip Mazowiecki, David Purser, Markus A. Whiteland · 2022
We consider linear cost-register automata (equivalent to weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems of boundedness and zero isolation ask whether there is a sequence of words that converge to infinity and to zero, respectively. In the general model both problems are undecidable so we focus on the copyless linear restriction. There, we show that the boundedness problem is decidable.