Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata

Clément Bertrand (1) , Cinzia Di Giusto (2) , Hanna Klaudel (3) , Damien Regnault (3)

1 Scalian Digital Systems
2 I3S - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis
3 IBISC - Informatique, BioInformatique, Systèmes Complexes

We study the complexity relationship between three models of unbounded memory automata: nu-automata (ν-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 ν-A.

Keywords: Memory automata; ν-automata; LaMA; HRA; Complexity; Non-emptiness; Membership; Theory of computation → Automata over infinite objects; Theory of computation → Problems; Reductions and completeness

Domains: Formal Languages and Automata Theory [cs.FL]

Clément Bertrand, Cinzia Di Giusto, Hanna Klaudel, Damien Regnault. Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata. 34th International Conference on Concurrency Theory (CONCUR 2023), Sep 2023, Antwerp, Belgium. ⟨10.4230/LIPIcs.CONCUR.2023.33⟩. ⟨hal-04199269⟩