Periodic Decomposition of Sequential Machines

Autor:	J. Robert Flexer, Arthur Gill
Rok vydání:	1967
Předmět:	Combinatorics Discrete mathematics Sequential machine Artificial Intelligence Hardware and Architecture Control and Systems Engineering Mod Greatest common divisor Partition (number theory) Finite set Software Information Systems Mathematics
Zdroj:	Journal of the ACM. 14:666-676
ISSN:	1557-735X 0004-5411
Popis:	Given a minimal sequential machine M and a positive integer T , it is desired to partition the state set of M into T classes, say S 0 , S 1 , · · ·, S T -1 , such that all states in S 1, under all possible inputs, pass into states in S i +1 (mod T ) . If such a T -partition exists, M can be realized by means of periodically-varying logic, which often results in the saving of memory elements. The period of M is defined as the greatest common divisor of all cycle lengths of M —a quantity which can be readily evaluated since it depends only on a finite set of independent loops exhibited by the state graph. The main result is that a T -partition exists for M if and only if T is a divisor of the period of M . For every such T , an algorithm is given for constructing the corresponding partition. If M is not required to be minimal, it is shown (constructively) that a T -partition exists for every T .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8e24f44e76ee10a255569069ba5e5bd0 https://doi.org/10.1145/321420.321425 Zobrazit plný text záznamu