Equivalence of Deterministic Weighted Real-time One-Counter Automata
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909393578098688 |
|---|---|
| author | Mathew, Prince Penelle, Vincent Saivasan, Prakash Sreejith, A. V. |
| author_facet | Mathew, Prince Penelle, Vincent Saivasan, Prakash Sreejith, A. V. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03066 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Equivalence of Deterministic Weighted Real-time One-Counter Automata Mathew, Prince Penelle, Vincent Saivasan, Prakash Sreejith, A. V. Formal Languages and Automata Theory F.1.1 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. |
| title | Equivalence of Deterministic Weighted Real-time One-Counter Automata |
| topic | Formal Languages and Automata Theory F.1.1 |
| url | https://arxiv.org/abs/2411.03066 |