Da-Ke He, Ashish Jagmohan, et al.
ISIT 2007
We present a "parenthesis-free" dialect of LISP, in which (a) each primitive function has a fixed number of arguments, and (b) the parentheses associating a primitive function with its arguments are implicit and are omitted. The parenthesis-free complexity of an S-expression e is defined to be the minimum size in characters {divides}p{divides} of a parenthesis-free LISP expression p that has the value e. We develop a theory of program-size complexity for parenthesis-free LISP by showing (a) that the maximum possible parenthesis-free complexity of an n-bit string is ∼ βn, and (b) how to construct three parenthesis-free LISP halting probabilities Ωpf, Ω′pf and Ω″pf. © 1992.
Da-Ke He, Ashish Jagmohan, et al.
ISIT 2007
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989