Equivalence of Deterministic Weighted Real-time One-Counter Automata

Autor:	Mathew, Prince, Penelle, Vincent, Saivasan, Prakash, A. V, Sreejith
Rok vydání:	2024
Předmět:	Computer Science - Formal Languages and Automata Theory F.1.1
Druh dokumentu:	Working Paper
Popis:	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 P. This paper gives a simpler proof and a better polynomial-time algorithm for checking the equivalence of two DWROCAs. Comment: 14 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2411.03066 Zobrazit plný text záznamu View this record from Arxiv