2016/10/24 by Thomas Kern, Kern, Thomas
Biochemistry, Genetics and Molecular Biology · Computer Science · #03D05 #DNA and Biological Computing #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1610.07535
openalex publication_date 2016/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
While automata theory often concerns itself with regular predicates, relations corresponding to acceptance by a finite state automaton, in this article we study the regular functions, such relations which are also functions in the set-theoretic sense. Here we present a small (but necessarily infinite) collection of (multi-ary) functions which generate the regular functions under composition. To this end, this paper presents an interpretation of the powerset determinization construction in terms of compositions of input-to-run maps. Furthermore, known results using the Krohn-Rhodes theorem to further decompose our generating set are spelled out in detail, alongside some coding tricks for dealing with variable length words. This will include two clear proofs of the Krohn-Rhodes Theorem in modern notation.