Set Augmented Finite Automata over Infinite Alphabets
arXiv:2311.06514
Abstract
A data language is a set of finite words defined on an infinite alphabet. Data languages are used to express properties associated with data values (domain defined over a countably infinite set). In this paper, we introduce set augmented finite automata (SAFA), a new class of automata for expressing data languages. We investigate the decision problems, closure properties, and expressiveness of SAFA. We also study the deterministic variant of these automata.
This is a full version of a paper with the same name accepted in DLT 2023. Other than the full proofs, this paper contains several new results concerning more closure properties, universality problem, comparison of expressiveness with several other automata models, and more results on deterministic SAFA