Ultimate-Definite and Symmetric-Definite Events and Automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Ultimate-Definite and Symmetric-Definite Events and Automata

Full text

Pdf (766 KB)

Source

Journal of the ACM (JACM) archive
Volume 12 , Issue 3 (July 1965) table of contents

Pages: 399 - 410

Year of Publication: 1965

ISSN:0004-5411

Authors

A. Paz	Technion, Israel Institute of Technology, Haifa
B. Peleg	The Hebrew University, Jerusalem

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 25, 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/321281.321292 What is a DOI?

ABSTRACT

New classes of events and finite automata which generalize the noninitial definite class are introduced. These events, called “ultimate definite” (u.d.), “reverse u.d.” and “symmetric definite,” are investigated as to algebraic and closure properties. Effective decision procedures whereby it can be decided whether a given finite automata defines such an event are given and unique canonical representations for these events are derived.

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	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]
	2	----. Canonical regular expressions and minimal state graphs for definite events. Proc. Syrup. on Mathematicl Theory of Automata, Polytechnic Institute of Brooklyn, 1962.
	3	----, AND McCLusKEY, E. J. Signal flow graph techniques for sequential circuit stae diagrams. IEEE Trans. EC-I2, 2(Apr. 1963), 67-76.
	4	KLEENE, S.C. Representation of events in nerve-nets and finite automata. In Autotta Studies, C. E. Shannon and J. McCarthy (Eds.), Princeton U. Press, 1954.
	5	McNAUGHTON, R., AND YAMADA, H. :Regular expressions and state graphs for automata. IRE Trans. EC-9 (1960), 39-47.
	6	PAz, A. Some aspects of probabilistic automata. In press.
	7	PERLES, M., RABIN, M. O., AND SHAMIR, E. The theory of definite automata. Tra. IRE EC (June 1963).
	8	RABIN, M.O. Probabilistic automata. Informat. Contr. 6, 3 (Sept. 1963).
	9	---, AND SCOTT, D. Finite automata and their decision problems, IBM J. Res. Develop. 3, 2 (Apr. 1959), 114-125.
	10	STEARNS, R. E., AND IARTMANIS, J. Regularity--preserving modifications of regular expressions. Informat. Contr. 6, 1 (1963).
	11	YOELI, M. Canonical representations of chain Events. MRC Tech. Sum. Rep. No. 462, Mar. 1964.

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
	R. G. Reynolds , W. F. Cutlip, Synchronizations and General Repetitive Machines, with Applications to Ultimate Definite Automata, Journal of the ACM (JACM), v.16 n.2, p.226-234, April 1969
	Balázs Imreh , Masami Ito, On regular languages determined by nondeterministic directable automata, Acta Cybernetica, v.17 n.1, p.1-10, January 2005
	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