On Decompositions of Regular Events
- 1 January 1969
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 16 (1) , 132-144
- https://doi.org/10.1145/321495.321505
Abstract
Decompositions of regular events into star events, i.e. events of the form W = V *, are studied. Mathematically, the structure of a star event is that of a monoid. First it is shown that every regular event contains a finite number of maximal star events, which are shown to be regular and can be effectively computed. Necessary and sufficient conditions for a regular event to be the union of its maximal star events are found. Next, star events are factored out from arbitrary events, yielding the form W - V * T . For each W there exists a unique largest V * and a unique smallest T ; an algorithm for finding suitable regular expressions for V and T is developed. Finally, an open problem of Paz and Peleg is answered: Every regular event is decomposable as a finite product of star events and prime events.Keywords
This publication has 4 references indexed in Scilit:
- Roots of Star EventsJournal of the ACM, 1967
- Ultimate-Definite and Symmetric-Definite Events and AutomataJournal of the ACM, 1965
- Derivatives of Regular ExpressionsJournal of the ACM, 1964
- Regularity preserving modifications of regular expressionsInformation and Control, 1963