Roots of star events
- 1 October 1966
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 7th Annual Symposium on Switching and Automata Theory (swat 1966)
Abstract
A regular event W is a star event iff there exists another event V such that W = V*. In that case, V is called a root of W. It is shown that every regular event has a unique minimum root, which is contained in every other root of W. An algorithm for finding the minimum root 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 6 references indexed in Scilit:
- Regular Expressions for Linear Sequential CircuitsIEEE Transactions on Electronic Computers, 1965
- 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
- Signal Flow Graph Techniques for Sequential Circuit State DiagramsIEEE Transactions on Electronic Computers, 1963
- A Survey of Regular Expressions and Their ApplicationsIRE Transactions on Electronic Computers, 1962