| Autor: |
Bertrand, Clément, Di Giusto, Cinzia, Klaudel, Hanna, Regnault, Damien |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We study the complexity relationship between three models of unbounded memory automata: nu-automata ($\nu$-A), Layered Memory Automata (LaMA)and History-Register Automata (HRA). These are all extensions of finite state automata with unbounded memory over infinite alphabets. We prove that the membership problem is NP-complete for all of them, while they fall into different classes for what concerns non-emptiness. The problem of non-emptiness is known to be Ackermann-complete for HRA, we prove that it is PSPACE-complete for $\nu$-A. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
