ON DECOMPOSITIONS OF REGULAR EVENTS

被引：14

作者：

BRZOZOWSKI, JA

COHEN, R

机构：

[1] University of Waterloo, Department of Applied Analysis and Computer Science, Waterloo, Ontario, Canada

来源：

JOURNAL OF THE ACM | 1969年 / 16卷 / 01期

关键词：

D O I：

10.1145/321495.321505

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. © 1969, ACM. All rights reserved.

引用

页码：132 / +

页数：1

共 8 条

[1] ROOTS OF STAR EVENTS [J].