Roots of Star Events

Abstract

A regular event W is a star event if there exists another event V such that W = V ^* . In that case, V is called a root of W . It is shown that every star event has a unique minimum root, which is contained in every other root. An algorithm for finding the minimum root of a regular event is presented, and the root is shown to be regular. The results have applications to languages, codes, canonical forms for regular expressions, simplification of expressions, decomposition of sequential machines, and semigroup theory.