Access Restriction

Author Brzozowski, J. A. ♦ Cohen, Rina
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1969
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Decompositions of regular events into star events, i.e. events of the form $\textit{W}$ = $\textit{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 $\textit{W}$ - $\textit{V}*\textit{T}.$ For each $\textit{W}$ there exists a unique largest $\textit{V}*$ and a unique smallest $\textit{T};$ an algorithm for finding suitable regular expressions for $\textit{V}$ and $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1969-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 16
Issue Number 1
Page Count 13
Starting Page 132
Ending Page 144

Open content in new tab

   Open content in new tab
Source: ACM Digital Library