Eunho Yang, Aurelie C. Lozano, et al.
ICML 2014
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.
Eunho Yang, Aurelie C. Lozano, et al.
ICML 2014
Gaku Yamamoto, Hideki Tai, et al.
AAMAS 2008
Rie Kubota Ando
CoNLL 2006
Erik Altman, Jovan Blanusa, et al.
NeurIPS 2023