A note on the emptiness problem for alternating finite-memory automata

We present alternative relatively simple and self-contained proofs of decidability of the emptiness problems for one-register alternating finite-memory automata and one-register alternating finite-memory tree automata.

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2014-03, Vol.526, p.97-107
Main Authors: Genkin, Daniel, Kaminski, Michael, Peterfreund, Liat
Format: Article
Language:English
Subjects:
Alternating finite-memory automata
Alternating finite-memory tree automata
Emptiness problem
Infinite alphabets
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present alternative relatively simple and self-contained proofs of decidability of the emptiness problems for one-register alternating finite-memory automata and one-register alternating finite-memory tree automata.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2014.01.020