FB 07 - Mathematik und Informatik, Physik, Geographie
Dauerhafte URI für den Bereich
Stöbern nach
Auflistung FB 07 - Mathematik und Informatik, Physik, Geographie nach Titel "Comments on Monoids Induced by NFAs"
Gerade angezeigt 1 - 1 von 1
Treffer pro Seite
Sortieroptionen
Item Comments on Monoids Induced by NFAs(2023-03) Holzer, MarkusWe summarize known results on the transformation monoid of nondeterministic finite automata (NFAs) from semigroup theory. In particular, we list what is known from the literature on the size of monoids induced by NFAs and their (minimal) number of generators - a comprehensive list of these generators is given in the Appendix. It is shown that any language accepted by an n-state NFA has a syntactic monoid of size at most 2^{n^2}. This bound is reachable by the generators of the semigroup B_n of n x n Boolean matrices with the usual matrix multiplication except that we assume 1 + 1 = 1. The number of these generators grows exponentially in n. This is a significant difference to the deterministic case, where three generators suffice to generate all elements of T_n. Moreover, we prove a lower bound for the \nfa-to-\dfa\ conversion using Lambert's W function.