Equivalence of Deterministic Weighted Real-Time One-Counter Automata
摘要
This paper introduces deterministic weighted real-time one-counter automaton (dwroca). A dwroca is a deterministic real-time one-counter automaton whose transitions are assigned a weight from a field. Two dwrocas are equivalent if every word accepted by one is accepted by the other with the same weight. dwroca is a sub-class of weighted one-counter automata with counter-determinacy. It is known that the equivalence problem for this model is in \(\textsf{P}\) [7]. This paper gives a simpler proof and a better polynomial-time algorithm for checking the equivalence of two dwrocas.