Generalized Cascade Decompositions of Automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generalized Cascade Decompositions of Automata

Full text

Pdf (797 KB)

Source

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

Pages: 411 - 422

Year of Publication: 1965

ISSN:0004-5411

Author

Michael Yoeli

Mathematical Sciences Department, Stanford Research Institute, Menlo Park, California

Publisher

ACM New York, NY, USA

Bibliometrics

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

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.321293 What is a DOI?

ABSTRACT

Incompletely specified (Mealy type) sequential machines and their generalizations to infinite machines are discussed. Convenient algebraic techniques for the study of such machines are introduced. These techniques are based on binary relations and on an extension of the usual concept of homomorphism to multivalued mappings. The first part of the paper gives a short, unified introduction to the algebraic theory of partial automata. The second part unifies and extends the algebraic approach to generalized cascade decompositions which combine conventional decomposition techniques with state-splitting procedures. The relationship between such generalized decompositions and state reductions of automata is investigated.

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	BIRKHOFF, G. Lattice Theory. Vol. 25, rev. ed., Amer. Math. See. Colloquium Publications, 1948.
	2	CLIFFORD, A. H., AND PRESTO, G.B. The Algebraic Theory of Semigroups, Vol. I. Math. Surveys No. 7, Amer. Math. See., Providence, R.I., 1961.
	3	Seymour Ginsburg, Introduction to Mathematical Machine Theory, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1982
	4	GINZBURG, A., AND YOELI, M. Products of automata and the problem of covering. Tech. Rep. No. 15, Technion, ttaifa, Israel, July 1963. {DDC Document No. AD-417380.
	5	HARTMANIS, J. Loop-free structure of sequential machines. Informat. Contr. 5 (Mar. 1962), 25-43.
	6	--, AND STEARNS, R. E. Some dangers in state reduction of sequential machines. Informat. Contr. 5 (Sept. 1962), 252-260.
	7	--, AND Pair algebra and its application to automata theory, lnformat. Contr. 7 (Dec. 1964), 485-507.
	8	Knsv, Z, Sezordary state assignment for sequeltial machines. IEEP2 Trans. ECq, (June 19G4), 193-203.
	9	PauIL M. C., and Lager nb S .H . Minimizing the number of states in incompletely specified sequntial switching functiors. IRE' Trans. EC-8 (Sept. t959), 35-367.
	10	Yoa, M. The cascade decomposition of sequential machines. IRE Trans. EC-IO (Dec 111-D, 587--.592.
	11	----, Casadeqarallel decompositions of sequential machines. IEEE Trans. EC-12 (aue 1961), 322 :24.
	12	-----I, compositions of finite automata. Tech llep. No. 10, Technion, Haifa, Israel (Mrch 1963). p{DD(3 Deumeit No. AD-406 302.
	13	Multiwdued homomorphie mappings and subdirect covers of partial algebras Tech. Sum. tlep. No. 493, Math, les. Ctr., US Army, Madison, Wis., July 1964.