2019/11/26 by Eija Jurvanen, Jurvanen, Eija, Magnus Steinby +1
Computer Science · #68Q45 (Primary) #68Q70 (Secondary) #Advanced Algebra and Logic #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, Reasoning, and Knowledge #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1911.11529
openalex publication_date 2019/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we introduce and study fuzzy deterministic top-down (DT) tree automata over a lattice L. The L-fuzzy tree languages recognized by these automata are said to be DT-recognizable, and they form a proper subfamily DRecL of the family of RecL of all regular L-fuzzy tree languages. We prove a Pumping Lemma for DRecL from which several decidability results follow. The closure properties of DRecL under various operations are established. We also characterize DT-recognizability in terms of L-fuzzy path languages, and prove that the path closure of any regular L-fuzzy tree language is DT-recognizable, and that it is decidable whether a regular L-fuzzy tree language is DT-recognizable. In most of the paper, L is just any nontrivial bounded lattice, but sometimes it is assumed to be distributive or even a bounded chain.