کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433753 | 689620 | 2015 | 21 صفحه PDF | دانلود رایگان |
For each regular language L we describe a family of canonical nondeterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for L in a locally finite variety VV, and apply an equivalence between the category of finite VV-algebras and a suitable category of finite structured sets and relations. By instantiating this to different varieties, we recover three well-studied canonical nfas: VV = boolean algebras yields the átomaton of Brzozowski and Tamm, VV = semilattices yields the jiromaton of Denis, Lemay and Terlutte, and V=Z2V=Z2-vector spaces yields the minimal xor automaton of Vuillemin and Gama. Moreover, we obtain a new canonical nfa called the distromaton by taking VV = distributive lattices. Each of these nfas is shown to be minimal relative to a suitable measure, and we derive sufficient conditions for their state-minimality. Our approach is coalgebraic, exhibiting additional structure and universal properties of the canonical nfas.
Journal: Theoretical Computer Science - Volume 604, 2 November 2015, Pages 81–101