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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Equivalence of Deterministic Weighted Real-Time One-Counter Automata

  • Prince Mathew,
  • Vincent Penelle,
  • Prakash Saivasan,
  • A. V. Sreejith

摘要

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.