B

C

BERTRAND , Clément

Last name: BERTRAND

First name: Clément

September 19, 2023 (v1)

Conference paper

Metadata-only

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

Bertrand, Clément Di Giusto, Cinzia Klaudel, Hanna

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...

Uploaded on: October 11, 2023
2023 (v1)

Report

Metadata-only

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

Bertrand, Clément Di Giusto, Cinzia Klaudel, Hanna

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...

Uploaded on: September 5, 2023