Absolute convergence of rational series is semi-decidable

摘要

This paper deals with absolute convergence of real-valued rational series, i.e. mappings r:Σ~*→R computed by weighted automata. An algorithm is provided, that takes a weighted automaton A as input and halts if and only if the corresponding series r_Ais absolutely convergent: hence, absolute convergence of rational series is semi-decidable. A spectral radius-like parameter ρr is introduced, which satisfies the following property: a rational series r is absolutely convergent iff ρr< 1. We show that if r is rational, then ρrcan be approximated by convergent upper estimates. Then, it is shown that the sum ∑_w∈Σ~*∣r(w)∣can be estimated to any accuracy rate. This result can be extended to any sum of the form ∑_w∈Σ~*∣r(w)∣~p, for any integer p.