DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA

Kosaburo Hashiguchi, Kenichi Ishiguro, Shuji Jimbo

International Journal of Algebra and Computation · 2002 · 24 citations · 4 references

Concepts

Abstract

A finance automaton is a sixtuple <Σ,Q,δ,S,F,f>, where <Σ,Q,δ,S,F> 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 : 2 Q × Σ * × 2 Q → 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.

References

4