Roots of Star Events
- 1 July 1967
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 14 (3) , 466-477
- https://doi.org/10.1145/321406.321409
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.Keywords
This publication has 3 references indexed in Scilit:
- Derivatives of Regular ExpressionsJournal of the ACM, 1964
- SemigroupsPublished by American Mathematical Society (AMS) ,1963
- Transition graphs and the star-height of regular events.The Michigan Mathematical Journal, 1963