Karan Bhanot, Ioana Baldini, et al.
AIES 2023
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.
Karan Bhanot, Ioana Baldini, et al.
AIES 2023
Susan L. Spraragen
International Conference on Design and Emotion 2010
Rocco Langone, Carlos Alzate, et al.
SSCI 2013
Chen-Yong Cher, Michael Gschwind
VEE 2008