Decidability of the equivalence problem of finitely ambiguous finance automata(Semigroups, Formal Languages and Computer Systems)
Kosaburo Hashiguchi, Kenichi Ishiguro · Institutional Repositories DataBase (IRDB) · 1996
A $\mathrm{f}\mathrm{i}_{11\mathrm{a}l}1\mathrm{C}\mathrm{e}$ automaton is a sixtuple $$ , where $$ is a finite automaton, $f$ : $Q\mathrm{x}\Sigma \mathrm{x}Q-R\cup\{-\infty\}$ is a finance function.$R$ is the set of real nulnbers and it holds $f(q, a, q)J=-\infty 1\mathrm{f}\mathrm{f}\sim q' ot\in\delta(q, \mathit{0})$ .The function $f$ is extended to $f$ : $2^{Q}\mathrm{x}\Sigma^{*}\mathrm{x}2^{Q}arrow R\cup\{-\infty)\}$ by the plus-max principle.For any $u$) $\in\underline{ abla}^{\pi}$ .$f(S.\mathrm{t}L.F)$ is the profit of $w$ .It is shown that the equivalence problem of finitely ambiguous finance automata is decidable.