2023/11/11 by Ansuman Banerjee, Banerjee, Ansuman, Kingshuk Chatterjee +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2311.06514
openalex publication_date 2023/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.