P.C. Yue, C.K. Wong
Journal of the ACM
An operator precedence language which is not real-time definable by any multitple Turing machine is constructed. This strengthens previous results about the existence of unambiguous context-free languages (CFL's) which are not real-time definable. In contrast, a family of CFL's of increasing degree of inherent ambiguity, each real-time definable by a one-tape Turing machine, is exhibited. In fact, an unboundedly ambiguous CFL, also real-time definable by a one-tape Turing machine, is presented. These results are the basis for the assertion that real-time definability of a CFL is independent from each of the structural properties considered. © 1968, ACM. All rights reserved.
P.C. Yue, C.K. Wong
Journal of the ACM
Zahra Ashktorab, Djallel Bouneffouf, et al.
IJCAI 2025
Vitaly Feldman
JMLR
Conrad Albrecht, Jannik Schneider, et al.
CVPR 2025