article

Free access

On Decompositions of Regular Events

Authors:

J. A. Brzozowski,

Rina CohenAuthors Info & Claims

Journal of the ACM (JACM), Volume 16, Issue 1

Pages 132 - 144

https://doi.org/10.1145/321495.321505

Published: 01 January 1969 Publication History

PDF eReader

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.

References

[1]

BRzozowsKI, J .A . Derivatives of regular expressions. J. ACM 1I, 4 (Oct. 1964), 481--494.

Crossref

Google Scholar

[2]

BRzozowsxI, J .A . Roots of star events. J. ACM 14, 3 (July 1967), 466-477.

Crossref

Google Scholar

[3]

HARTMANIS, J., AND STEARNS, R .E . Algebraic Structure Theory of Sequential Machine. Prentice-Hall, Englewood Cliffs, N. J., 1966.

Crossref

Google Scholar

[4]

PAZ, A., AND PmJEG, B. On concatenative decompositions of regular events. IEEE Trans. EC-17 (Mar. 1968), 229-237.

Google Scholar

[5]

PAZ, A., AND PELEG, B. Ultimate-definite and symmetric-definite events and automata. J. ACM 12, 3 (July 1965), 399-410.

Crossref

Google Scholar

[6]

STEARNS, R. E., AND HAWrMANIS, J. Regularity preserving modifications of regular expressions. Inform. Contr. 6 (1963), 55-69.

Crossref

Google Scholar

[7]

LJAPIN, E. S. Semigroups. Translations of Math. Monographs (3). Amer. Math. Sot., Providence, R. I., 1963.

Google Scholar

[8]

RABIN, M. O., AND SCOTT, D. Finite automata and their decision problems, IBM J. Res. Dev. 8, 2 (Apr. 1959), 114-125.

Google Scholar

Cited By

View all

Ködding MTruthe B(2024)Various Types of Comet Languages and their Application in External Contextual GrammarsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.407.9407(118-135)Online publication date: 11-Sep-2024
https://doi.org/10.4204/EPTCS.407.9
Cotumaccio ND’Agostino GPolicriti APrezza N(2023)Co-lexicographically Ordering Automata and Regular Languages - Part IJournal of the ACM10.1145/360747170:4(1-73)Online publication date: 12-Aug-2023
https://dl.acm.org/doi/10.1145/3607471
Kutrib MWendlandt M(2017)Concatenation-free languagesTheoretical Computer Science10.1016/j.tcs.2016.08.014679:C(83-94)Online publication date: 30-May-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.08.014
Show More Cited By

Index Terms

On Decompositions of Regular Events
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Logic

Recommendations

On decompositions of regular events
FOCS '67: Proceedings of the 8th Annual Symposium on Switching and Automata Theory (SWAT 1967)

This paper studies decompositions of regular events into star events, i.e. events of the form W = V*. 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 ...
On Concatenative Decompositions of Regular Events

Abstract Finding simple or "canonical representations" for regular events is one of the important problems concerning finite automata. The present paper is an attempt to find concatenative canonical decompositions for regular events. Five different ...
Regular Transducer Expressions for Regular Transformations
LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

Functional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show that every regular function, either on finite words or on infinite words, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 16, Issue 1

Jan. 1969

177 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321495

Editor:
Gerard Salton
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1969

Published in JACM Volume 16, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
469
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)6

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ködding MTruthe B(2024)Various Types of Comet Languages and their Application in External Contextual GrammarsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.407.9407(118-135)Online publication date: 11-Sep-2024
https://doi.org/10.4204/EPTCS.407.9
Cotumaccio ND’Agostino GPolicriti APrezza N(2023)Co-lexicographically Ordering Automata and Regular Languages - Part IJournal of the ACM10.1145/360747170:4(1-73)Online publication date: 12-Aug-2023
https://dl.acm.org/doi/10.1145/3607471
Kutrib MWendlandt M(2017)Concatenation-free languagesTheoretical Computer Science10.1016/j.tcs.2016.08.014679:C(83-94)Online publication date: 30-May-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.08.014
Gange GNavas JSchachte PSøndergaard HStuckey P(2016)A complete refinement procedure for regular separability of context-free languagesTheoretical Computer Science10.1016/j.tcs.2016.01.026625:C(1-24)Online publication date: 25-Apr-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.01.026
Kutrib MWendlandt M(2015)Expressive Capacity of Concatenation FreenessImplementation and Application of Automata10.1007/978-3-319-22360-5_17(199-210)Online publication date: 28-Jul-2015
https://doi.org/10.1007/978-3-319-22360-5_17
Holzer MKutrib MMeckel K(2011)Nondeterministic state complexity of star-free languagesProceedings of the 16th international conference on Implementation and application of automata10.5555/2032366.2032385(178-189)Online publication date: 13-Jul-2011
https://dl.acm.org/doi/10.5555/2032366.2032385
Holzer MKutrib MMeckel K(2011)Nondeterministic State Complexity of Star-Free LanguagesImplementation and Application of Automata10.1007/978-3-642-22256-6_17(178-189)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22256-6_17
Bordihn HHolzer MKutrib M(2009)Determination of finite automata accepting subregular languagesTheoretical Computer Science10.1016/j.tcs.2009.05.019410:35(3209-3222)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.05.019
Afonin SGolomazov D(2009)Minimal Union-Free Decompositions of Regular LanguagesProceedings of the 3rd International Conference on Language and Automata Theory and Applications10.1007/978-3-642-00982-2_7(83-92)Online publication date: 31-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-00982-2_7
AFONIN SKHAZOVA E(2006)MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGESInternational Journal of Foundations of Computer Science10.1142/S012905410600395417:03(493-506)Online publication date: Jun-2006
https://doi.org/10.1142/S0129054106003954
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations