TY - JOUR
T1 - Decidability of the equivalence problem for finitely ambiguous finance automata
AU - Hashiguchi, Kosaburo
AU - Ishiguro, Kenichi
AU - Jimbo, Shuji
PY - 2002
Y1 - 2002
N2 - 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 : 2Q × Σ* × 2Q → R ∪ {- ∞} by the plus-max principle. For any ω ∈ Σ*, f(S, ω, F) is the profit of ω. It is shown that the equivalence problem for finitely ambiguous finance automata is decidable.
AB - 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 : 2Q × Σ* × 2Q → R ∪ {- ∞} by the plus-max principle. For any ω ∈ Σ*, f(S, ω, F) is the profit of ω. It is shown that the equivalence problem for finitely ambiguous finance automata is decidable.
KW - Finance automata
KW - Plus-max principle
KW - Transducer
KW - Tropical semiring
UR - http://www.scopus.com/inward/record.url?scp=0035998625&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035998625&partnerID=8YFLogxK
U2 - 10.1142/S0218196702000845
DO - 10.1142/S0218196702000845
M3 - Article
AN - SCOPUS:0035998625
SN - 0218-1967
VL - 12
SP - 445
EP - 461
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 3
ER -