Roots of Star Events

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Roots of Star Events

Full text

Pdf (628 KB)

Source

Journal of the ACM (JACM) archive
Volume 14 , Issue 3 (July 1967) table of contents

Pages: 466 - 477

Year of Publication: 1967

ISSN:0004-5411

Author

J. A. Brzozowski

Department of Electrical Engineering, University of Ottawa, Ottawa, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 27, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321406.321409 What is a DOI?

ABSTRACT

A regular event W is a star event if there exists another event V such that W = V*. In that case, V is called a root of W. It is shown that every star event has a unique minimum root, which is contained in every other root. An algorithm for finding the minimum root of a regular event 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	LJAPIN, E.S. Semigroups. Translations of Math. Monographs, No. 3, Amer. Math. Soe., Providence, R. I., 1963.
	2	CLIFFORD, A. H., AND PRESTON, G.B. The Algebraic Theory of Semigroups. Malh. Serveys series, Vol. I. Amer. Math. Soe., Providence, R. I., 1961.
	3	Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964 [doi>10.1145/321239.321249]
	4	PAZ, A., AND PELEG, B. Concatenative decompositions of regular events. Tech. Rep. No, 20, The Hebrew University, Jerusalern, Israel, 1965.
	5	BRzozowsKL J, A. Regular expressions for linear sequential circuits. IEEE Trans. EC- 14, 2 (April 1965), 148-156.
	6	--- AND McCLUSKEY, E. J., JR. Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. EC-I2, 2 (April 1963), 67-76.
	7	EGGAN, L.C. Transition graphs and star height of regular events. Mich. Malh. J. 10 (1963), 385-397.
	8	EVEN, S. On information lossless automata. Ph.D. dissertation, Harvard U., Cambridge, Mass., 1963,
	9	BRZOZOWSKI, J. A. A survey of regular expressions and their applications. IRE Trans. EC-II, 3 (June 1962), 324-335.

CITED BY 4

	J. A. Brzozowski , Rina Cohen, On Decompositions of Regular Events, Journal of the ACM (JACM), v.16 n.1, p.132-144, Jan. 1969
	K. Culik, II, A Purely Homomorphic Characterization of Recursively Enumerable Sets, Journal of the ACM (JACM), v.26 n.2, p.345-350, April 1979
	Peter Johansen, Free groups and regular expressions, Proceedings of the first annual ACM symposium on Theory of computing, p.113-128, May 05-07, 1969, Marina del Rey, California, United States
	Henning Bordihn , Markus Holzer , Martin Kutrib, Determination of finite automata accepting subregular languages, Theoretical Computer Science, v.410 n.35, p.3209-3222, August, 2009