A compensation cost analysis of service-aggregate transaction for DTNs clients

Clients from Delay Tolerant Networks (DTNs) might encounter overtime exceptions when they aggregate autonomic commercial web service references to form an all-or-nothing transaction. Such exceptions may cause extra overhead—“compensation cost” when aborting transactions. Regarding the delay-related characteristics of DTNs, this paper models the expected compensation cost (ECC) for the schedulings of commit-requests, presents a calculability analysis for quantitative ECC prediction, and explores the limitation of ECC’s probabilistic prediction accordingly. The analysis is based on the timed-2PC plus compensation (t2PC+) protocol and the multi-step price tag pattern, which is verified conditionally by simulation tests through randomly-chosen severely-fluctuant samplings of compensation cost and delays. The ultimate target of this work is to demonstrate the high complexity, and in particular, the uncertainty of ECC predictions due to the randomicity of DTNs’ delays.     

Distributed computing on oriented anonymous hypercubes with faulty components

We give efficient algorithms for distributed computation on oriented, anonymous, asynchronous hypercubes with possible faulty components (i.e. processors and links) and deterministic processors. Initially, the processors know only the size of the network and that they are inter-connected in a hypercube topology. Faults may occur only before the start of the computation (and that despite this the hypercube remains a connected network). However, the processors do not know where these faults are located. As a measure of complexity we use the total number of bits transmitted during the execution of the algorithm and we concentrate on giving algorithms that will minimize this number of bits. The main result of this paper is an algorithm for computing Boolean functions on anonymous hypercubes with bit cost , where is the number of faulty components (i.e. links plus processors), is the number of links which are either faulty, or non-faulty but adjacent to faulty processors, and is the diameter of the hypercube with faulty components. Received: October 1992 / Accepted: April 2001     

Weakly useful sequences

An infinite binary sequence x is defined to be

(i) strongly useful if there is a computable time bound within which every decidable sequence is Turing reducible to x; and

(ii) weakly useful if there is a computable time bound within which all the sequences in a non-measure 0 subset of the set of decidable sequences are Turing reducible to x.

Juedes, Lathrop, and Lutz [Theorectical Computer Science 132 (1994) 37] proved that every weakly useful sequence is strongly deep in the sense of Bennett [The Universal Turing Machine: A Half-Century Survey, 1988, 227] and asked whether there are sequences that are weakly useful but not strongly useful. The present paper answers this question affirmatively. The proof is a direct construction that combines the martingale diagonalization technique of Lutz [SIAM Journal on Computing 24 (1995) 1170] with a new technique, namely, the construction of a sequence that is “computably deep” with respect to an arbitrary, given uniform reducibility. The abundance of such computably deep sequences is also proven and used to show that every weakly useful sequence is computably deep with respect to every uniform reducibility.

关于自然语言计算机处理的几点思考

自然语言处理是人类在信息时代探索自我的必然,为此应将其看作为人类认识自我进程中的一个环节.本文结合其他学科,简要探讨了有关语言和智能,语言是否可以计算,语义和分解,歧义与知识等基本问题.     

Characterizing Programming Systems Allowing Program Self-Reference

The interest is in characterizing insightfully the power of program self-reference in effective programming systems ( ), the computability-theoretic analogs of programming languages (for the partial computable functions). In an in which the constructive form of Kleene’s Recursion Theorem (KRT) holds, it is possible to construct, algorithmically, from an arbitrary algorithmic task, a self-referential program that, in a sense, creates a self-copy and then performs that task on the self-copy. In an in which the not-necessarily-constructive form of Kleene’s Recursion Theorem (krt) holds, such self-referential programs exist, but cannot, in general, be found algorithmically. In an earlier effort, Royer proved that there is no collection of recursive denotational control structures whose implementability characterizes the in which KRT holds. One main result herein, proven by a finite injury priority argument, is that the in which krt holds are, similarly, not characterized by the implementability of some collection of recursive denotational control structures. On the positive side, however, a characterization of such of a rather different sort is shown herein. Though, perhaps not the insightful characterization sought after, this surprising result reveals that a hidden and inherent constructivity is always present in krt. This paper is an expanded version of [6]. This paper received support from NSF Grant CCR-0208616. “Know thyself.” Greek proverb     

Computability versus exact computability of martingales

This note gives a simple example of a polynomial-time computable martingale that has rational values but is not exactly computable.     

Model discrimination using an algorithmic information criterion

A method of choosing between competing models of small sets of observations is presented. The intended application is to the modelling of ‘badly defined’ systems. The ideas of algorithmic information theory are surveyed, and applied to model discrimination. A novel definition of a model as a program which computes the observations exactly is given; this allows the size of a model to be interpreted as a measure of the informativeness of the model. It also imposes a trade-off between approximation and complexity, which is essential if overfitting of models is to be avoided. Two examples of discriminating between models of field data are presented.     

The computable kernel of Abstract State Machines

Abstract State Machines (ASMs) were introduced as “a computation model that is more powerful and more universal than standard computation models”, by Yuri Gurevich in 1985. ASMs gained much attention as a specification method. It is extremely flexible because any mathematical structure may serve as a state. Gurevich characterized the expressive power of ASMs in terms of intuitively convincing postulates.     

Calculs sur les structures de langage dénombrable

We develop two models of calculus over stuctures of countable signature and the main items of the “structural complexity theory” which relates to them. In particular, we prove the existence of universal machines, complete problems, and structures with the P = NP property. In this frame, we are starting the study of -group without order and the field of p-adic numbers .