Identity delegation in policy based systems
Rajeev Gupta, Shourya Roy, et al.
ICAC 2006
Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the program-size complexity relative to n of its n-bit prefixes xn. Meyer has shown that x is recursive iff ∃c, ∀n, K(xn{plus 45 degree rule}n) ≤ c, and Loveland has shown that this is false if one merely stipulates that K(xn{plus 45 degree rule}n) ≤ c for infinitely many n. We strengthen Meyer's theorem. From the fact that there are few minimal-size programs for calculating n given result, we obtain a necessary and sufficient condition for x to be recursive in terms of the absolute program-size complexity of its prefixes: x is recursive iff ∃c, ∀n, K(xn) ≤ K(n) + c. Again Loveland's method shows that this is no longer a sufficient condition for x to be recursive if one merely stipulates that K(xn) ≤ K(n) + c for infinitely many n. © 1976.
Rajeev Gupta, Shourya Roy, et al.
ICAC 2006
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
Robert E. Donovan
INTERSPEECH - Eurospeech 2001
Fan Zhang, Junwei Cao, et al.
IEEE TETC