scientific article; zbMATH DE number 3932413
[For the entire collection see Zbl 0552.00014.] If L is a rational language \((=regular\) set) over the alphabet A, then the author constructs a graph \(\Gamma\) (L) from the minimal automaton accepting L. The graph \(\Gamma\) (L) has two types of labeled arrows. These arrows encode different factorizations of words in L, with the result that certain loops in \(\Gamma\) (L) indicate that some word in \(A^*\) has two distinct factorizations into words from L. Hence L is not a code. The author shows that one need only check for loops of lengths up to \((n^ 2+n)/2\), where n is the number of states in the finite automaton accepting L. He makes further application to finding the free submonoid of \(A^*\) generated by L, i.e., the minimal free submonoid of \(A^*\) containing \(L^*\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3704907)