ON LOWER BOUND TO MEMORY OF FINITE STATE MACHINES

被引：3

作者：

VAIRAVAN, K

机构：

[1] Department of Electrical Engineering, University of Wisconsin, Milwaukee

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1969年 / C 18卷 / 09期

关键词：

D O I：

10.1109/T-C.1969.222782

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A finite state machine (FSM) is said to have finite memory µ if µ is the least integer such that yk=f(xk, xk-1,…,xk-μ, yk-1, … μk-u) where yk and xkrepresent the output and input at time k. If no such µ exists, then by convention the memory is said to be infinite. It has been observed [1] that if the memory of a p-nary input, q-nary output n-state minimal nondegenerate FSM is finite, then the memory µ is bounded as follows. © 1969 IEEE. All rights reserved.

引用

页码：856 / &

共 50 条

[21] A Lower Bound for the Optimization of Finite Sums
Agarwal, Alekh
Bottou, Leon
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 37, 2015, 37 : 78 - 86
[22] FINITE STATE MACHINES IN STATE ESTIMATION FOR DYNAMIC-SYSTEMS WITH AN NTH ORDER MEMORY AND NONLINEAR INTERFERENCE
DEMIRBAS, K
JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS, 1989, 326 (06): : 817 - 829
[23] Finite barrier bound state
Liu, Tao
Bai, Kai
Zhang, Yicheng
Wan, Duanduan
Lai, Yun
Chan, C. T.
Xiao, Meng
LIGHT-SCIENCE & APPLICATIONS, 2024, 13 (01)
[24] Finite barrier bound state
Tao Liu
Kai Bai
Yicheng Zhang
Duanduan Wan
Yun Lai
C. T. Chan
Meng Xiao
Light: Science & Applications, 13
[25] An Improved Upper Bound for the Length of Preset Distinguishing Sequences of Distinguished Merging Finite State Machines
Gunicen, Canan
Inan, Kemal
Turker, Uraz Cengiz
Yenigun, Husnu
INFORMATION SCIENCES AND SYSTEMS 2014, 2014, : 325 - 335
[26] CONTINUOUS STATE MODELS FOR FINITE STATE MACHINES
PORTER, WA
INTERNATIONAL JOURNAL OF CONTROL, 1977, 25 (02) : 165 - 183
[27] OPTIMAL STATE ASSIGNMENT FOR FINITE STATE MACHINES
DEMICHELI, G
BRAYTON, RK
SANGIOVANNIVINCENTELLI, A
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1985, 4 (03) : 269 - 285
[28] A state assignment algorithm for finite state machines
Skias, D
Haniotakis, T
Tsiatouhas, Y
Arapoyanni, A
ICECS 2000: 7TH IEEE INTERNATIONAL CONFERENCE ON ELECTRONICS, CIRCUITS & SYSTEMS, VOLS I AND II, 2000, : 823 - 826
[29] State assignment of finite-state machines
Ahmad, I
Dhodhi, MK
IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, 2000, 147 (01): : 15 - 22
[30] SOME COMMENTS ON GENERALIZED SHANNON LOWER BOUND FOR STATIONARY FINITE-ALPHABET SOURCES WITH MEMORY
YAO, K
TAN, H
IEEE TRANSACTIONS ON INFORMATION THEORY, 1973, 19 (06) : 815 - 817

← 1 2 3 4 5 →