Absolute Convergence of Rational Series Is Semi-decidable

摘要

We study real-valued absolutely convergent rational series, i.e. functions r : ∑~* → R, denned over a free monoid ∑~*, that can be computed by a multiplicity automaton A and such that ∑_(w∈∑~*)|r(w)| < ∞. We prove that any absolutely convergent rational series r can be computed by a multiplicity automaton A which has the property that r_(|A|) is simply convergent, where r_(|A|) is the series computed by the automaton (|A|) derived from A by taking the absolute values of all its parameters. Then, we prove that the set A~(rat)(∑) composed of all absolutely convergent rational series is semi-decidable and we show that the sum ∑_(w∈∑~*)|r(w)| can be estimated to any accuracy rate for any r ∈ A~(rat)(∑). We also introduce a spectral radius-like parameter ρ_(|r|) which satisfies the following property: r is absolutely convergent iff ρ_(|r|) < 1.