Weiming Hu, Nianhua Xie, et al.
IEEE TPAMI
Any sequential machine M represents a function fM from input sequences to output symbols. A function f is representable if some finite-state sequential machine represents it. The function fM is called an n-th order approximation to a given function f if fM is equal to f for all input sequences of length less than or equal to n. It is proved that, for an arbitrary nonrepresentable function f, there are infinitely many n such that any sequential machine representing an nth order approximation to f has more than n/2 + 1 states. An analogous result is obtained for two-way sequential machines and, using these and related results, lower bounds are obtained for two-way sequential machines and, using these and related results, lower bounds are obtained on the amount of work tape required online and offline Turing machines that compute nonrepresentable functions. © 1967, ACM. All rights reserved.
Weiming Hu, Nianhua Xie, et al.
IEEE TPAMI
Cynthia Dwork, Moni Naor, et al.
Journal of the ACM
Junchen Jiang, Yue Zhu
OSSNA 2025
Khalid Abdulla, Andrew Wirth, et al.
ICIAfS 2014