DocumentCode
2199970
Title
Universal two state machines: Characterization theorems and decomposition schemes
Author
Ullman, J.D. ; Weiner, P.
fYear
1968
fDate
15-18 Oct. 1968
Firstpage
413
Lastpage
426
Abstract
In the first part of this paper, an algorithm is derived for testing a given two state machine for the property of being universal. Various characterizations of universality are also obtained, and are stated in the form of necessary and sufficient conditions. The second part of this paper is concerned with the economical realization of sequential machines as networks of identical modules. Bounds are derived for the number of copies of a certain universal modules needed for the realization of an arbitrary machine selected from a given class.
Keywords
Clocks; Fabrication; Integrated circuit interconnections; Labeling; Laboratories; Sufficient conditions; Telephony; Testing; Timing; Wire;
fLanguage
English
Publisher
ieee
Conference_Titel
Switching and Automata Theory, 1968., IEEE Conference Record of 9th Annual Symposium on
Conference_Location
Schenedtady, NY, USA
ISSN
0272-4847
Type
conf
DOI
10.1109/SWAT.1968.43
Filename
4569589
Link To Document