DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
Kosaburo Hashiguchi, Kenichi Ishiguro, Shuji Jimbo · International Journal of Algebra and Computation · 2002
A finance automaton is a sixtuple , where is a (non-deterministic) finite automaton, f : Q × Σ × Q → R ∪ {-∞} is a finance function, R is the set of real numbers and f(q,a,q′) = -∞ if and only if q′∉δ(q,a). The function f is extended to f : 2Q × Σ* × 2Q → R ∪ {-∞} by the plus-max principle. For any w ∈ Σ*, f (S,w,F) is the profit of w. It is shown that the equivalence problem for finitely ambiguous finance automata is decidable.