Name
Abstract | ||
|---|---|---|
Gill[1] has shown that if there exists a finite-memory n-state sequential machine with finite memory 驴, then 驴 cannot exceed 陆n(n-1)驴Nn. He has further shown[2] that there exists an n-state Nn input-binary output machine with memory 驴= Nn for every n. The question of whether a tighter upper bound might be placed on 驴 by the order of the input alphabet was raised by Gill. Massey[3] recently has shown that there exists a ternary input-binary output finite-memory machine with memory 驴=Nn for every n. The primary purpose of this note is to show that for every n there exists an n-state binary input-binary output finite-memory machine with memory 驴= Nn, and thus 驴 is shown not to be limited by the order of the input alphabet. It is shown that for every n there are actually at least two different machines with memory 驴 = Nn. It will also be shown that for every n there exists a binary input-binary output n-state finite-memory machine with 驴 = Nn-1. |
Year | DOI | Venue |
|---|---|---|
1968 | 10.1109/TC.1968.5008872 | IEEE Trans. Computers |
Keywords | Field | DocType |
Construction industry,Data mining,Computers,Probability density function,Arrays,Artificial neural networks | Combinatorics,Computer science,Upper and lower bounds,Sequential machine,Parallel computing,Algorithm,Ternary operation,Construction industry,Artificial neural network,Binary number,Alphabet | Journal |
Volume | Issue | ISSN |
17 | 1 | 0018-9340 |
Citations | PageRank | References |
7 | 1.15 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Monroe M. Newborn | 1 | 177 | 47.49 |