In this paper, we introduce the formalism of deduction graphs as a generalisation of both Gentzen-Prawitz style natural deduction and Fitch style flag deduction. The advantage of this formalism is that, as with flag d...
详细信息
In this paper, we introduce the formalism of deduction graphs as a generalisation of both Gentzen-Prawitz style natural deduction and Fitch style flag deduction. The advantage of this formalism is that, as with flag deductions (but not natural deduction), subproofs can be shared, but the linearisation used in flag deductions is avoided. Our deduction graphs have both nodes and boxes, which are collections of nodes that also form a node themselves. This is reminiscent of the bigraphs of Milner, where the link graph describes the nodes and edges and the place graph describes the nesting of nodes. We give a precise definition of deduction graphs, together with some illustrative examples. Furthermore, we analyse their computational behaviour by studying the process of cut-elimination and by defining translations from deduction graphs to simply typed lambda terms. From a slight variation of this translation, we conclude that the process of cut-elimination is strongly normalising. The translation to simple type theory removes quite a lot of structure, so we also propose a translation to a context calculus with lets that faithfully captures the structure of deduction graphs. The proof nets of linear logic also offer a graph-like presentation of natural deduction, and we point out some similarities between the two formalisms.
Some of the early work on in-network computation, a term that is being applied to this class of problems, was on the asymptotic analysis of the number of transmissions needed to compute specific functions in noisy bro...
详细信息
Some of the early work on in-network computation, a term that is being applied to this class of problems, was on the asymptotic analysis of the number of transmissions needed to compute specific functions in noisy broadcast networks. The development of geometric random graph theory and its applicability to wireless networks led to an extending of the analysis to large, multihop wireless networks. A second approach, which in some sense predates the preceding class of problems, considers simple, we may even say simplistic, networks with a small number of correlated sources. A third approach is to analyze the communication complexity of computing functions. The preceding is a sample of the extant literature and we launched this special issue with the hope of consolidating the area and also provide a launch-pad for new problem formulations and applications. We are happy to note that we have been reasonably successful on both counts and this special issue contains papers that advance our understanding of the fundamental limits and also develop several interesting new strands of research. And there are also papers that analyze the performance of in-network computation in specific application environments.
An analogy calculus (LK(A)) is proposed in this paper. Some important theorems, such as cut-elimination, interpolation, are proved. The model semantics of LK(A) is also proposed. Based on LK(A), analogy is defined as ...
详细信息
An analogy calculus (LK(A)) is proposed in this paper. Some important theorems, such as cut-elimination, interpolation, are proved. The model semantics of LK(A) is also proposed. Based on LK(A), analogy is defined as equivalence-provable in LK(A) from an analogy correspondence.
This paper studies a novel dissimilar coaxial rotor concept with significantly reduced rotor-rotor aerodynamic interaction during hovering flight. The proposed concept's performance is systematically compared with...
详细信息
This paper studies a novel dissimilar coaxial rotor concept with significantly reduced rotor-rotor aerodynamic interaction during hovering flight. The proposed concept's performance is systematically compared with regular coaxial and conventional single rotor configurations using 1) analytical and 2) blade element momentum theory (BEMT)-based analysis for hover flight condition. The hover performance among different rotor configurations is compared using a baseline main rotor combined with various antitorque mechanisms. Through this study it is established that the dissimilar coaxial rotor configuration shows improved performance for torque equilibrium cases when compared to both conventional and regular coaxial configurations for moderate- to high-thrust conditions with power reduction of 16-37% when compared to a conventional single main rotor-tail rotor configuration and 14-17% of power saving when compared to a regular coaxial rotor during hovering flight with rotor thrust in the range of 0.004 < C-T < 0.01. The analytical method from momentum theory and BEMT results correlate well for the induced and profile torque balanced conditions. The proposed concept appears to be an efficient alternative to the conventional single main rotor with tail rotor and regular coaxial rotor for hovering flight conditions within the scope of the analysis.
Structures exhibiting strong comprehension properties have been utilized in different fields of Mathematical Logic and Theoretical Computer Science. Although the techniques employed and the intended applications are q...
详细信息
Structures exhibiting strong comprehension properties have been utilized in different fields of Mathematical Logic and Theoretical Computer Science. Although the techniques employed and the intended applications are quite different, these structures are essentially alike. Starting from a general definition of Hyperuniverse, we present here a comprehensive framework for investigating these structures. We also give a procedure for constructing Hyperuniverses which encompasses all known examples and provides many new non-epsilon-isomorphic and even non-homeomorphic structures.
The infrared structure of (multi-loop) scattering amplitudes is determined entirely by the identities of the external particles participating in the scattering. The two-loop infrared structure of pure QCD amplitudes h...
详细信息
The infrared structure of (multi-loop) scattering amplitudes is determined entirely by the identities of the external particles participating in the scattering. The two-loop infrared structure of pure QCD amplitudes has been known for some time. By computing the two-loop amplitudes for (f) over barf -> X and (f) over barf -> V1V2 scattering in an SU(N) x SU(M) x U(1) gauge theory, I determine the anomalous dimensions which govern the infrared structure for any massless two-loop amplitude.
This paper is concerned with an effective hierarchy of guaranteed processes. A process satisfies a guarantee requirement when that requirement holds at some forthcoming point of every computation. Sigma(1)(0) being th...
详细信息
This paper is concerned with an effective hierarchy of guaranteed processes. A process satisfies a guarantee requirement when that requirement holds at some forthcoming point of every computation. Sigma(1)(0) being the class of omega-languages accepted by the base of this process hierarchy, this class of processes, namely O-1, is a class of universal machines. Translated in these terms, our results throw light on, first, the increased computational power of the machine resulting from communication between any finite number of such machines and, second, that the hierarchy whose next degree represents omega-languages accepted by machines resulting from communication between any finite number of machines in the current degree, is infinite. Interaction product acts as jump operator. We naturally start with some effective classes of guarantee properties proven to form a hierarchy and first prove that they have not the separation property. A class C of omega-languages has the separation property if, for any pair (U, V) in C, there exists an omega-language W is an element of C such that U boolean AND W = 0 double left right arrow V boolean AND W not equal 0. We then induce non-separability under testing from the above language theoretic non-separability result. Two processes are said to be separable if they can be separated from each other by means of another test process from the same class. It finally turns out that some processes, having different visible behaviours, are test equivalent. We close the paper on logical complexity issues of the testing problem when test criteria and guarantee constraints range over the arithmetical hierarchy.
A number of memoisation techniques io eliminate computational redundancy from a large and automatically detectable class of nonlinear functions are introduced. The techniques make use of memo-tables and memo-functions...
详细信息
A number of memoisation techniques io eliminate computational redundancy from a large and automatically detectable class of nonlinear functions are introduced. The techniques make use of memo-tables and memo-functions to improve the run time efficiency of functions exhibiting commutative redundancy. A memo-function remembers all the arguments to which it has been applied, together with the corresponding results from them, by storing them in a memo-table. The schemes discussed use a separate transient memo-table for each high-level application of the function. This contrasts with the technique of full memoisation, in which memo-tables are persistent. A basic memoisation scheme is introduced that is further refined to give a number of other more efficient strategies to reduce the growth of these tables during evaluation. These strategies make use of the nature of the dependency graph of functions exhibiting commutative redundancy to make intelligent decisions concerning memo-table insertion and deletion operations. More precisely, the level of sharing of nodes in the dependency graph of functions is used to expedite the deletion of obsolete memo-table entries. When compared to contemporary program transformation schemes, the techniques presented achieve comparable improvements in efficiency while being mechanical. In addition, these techniques are more generally applicable and require less compile-time deductive capacity than the corresponding program transformation schemes. The paper also outlines an application of one of the techniques to Queueing Networks.
We give a characterization of morphisms which preserve finite and infinite standard Sturmian words. The class of such morphisms coincides with the monoid {D,E}* of the endomorphisms of A*, where A = {a,b}, generated b...
详细信息
We give a characterization of morphisms which preserve finite and infinite standard Sturmian words. The class of such morphisms coincides with the monoid {D,E}* of the endomorphisms of A*, where A = {a,b}, generated by the two elementary morphisms, E which interchanges the letter a with b and D which is the Fibonacci morphism defined as: D(a)= ab,D(b) = a. Some new properties of these morphisms are shown. In particular, we prove the following result: Let {X-n}(n greater than or equal to 0) be the sequence of sets inductively defined as :X-0 = {epsilon}, X-1 = {a}, Xn+1 = (AX(n))((-)) for n > 1, where E denotes the empty word and (-) is the operator of left-palindrome closure associating to each word w the shortest word having Mi as suffix. For all n greater than or equal to one has: Xn+1 = ((E boolean OR l)o D)(X-n)a, where I denotes the identity map. From this we derive a new characterization of the set PER of all words w having two periods p and q which are coprimes and such that \w\ = p + q - 2. Indeed, one has that PER boolean AND aA* = boolean OR ((E boolean OR l)o D)(X-n)a.
We consider the problem of aligning of k sequences of length n. The cost function is sum of pairs, and satisfies triangle inequality. Earlier results on finding approximation algorithms for this problem are due to Gus...
详细信息
We consider the problem of aligning of k sequences of length n. The cost function is sum of pairs, and satisfies triangle inequality. Earlier results on finding approximation algorithms for this problem are due to Gusfield (1991) who achieved an approximation ratio of 2 - 2/k, and Pevzner (1992) who improved it to 2 - 3/k. We generalize this approach to assemble an alignment of k sequences from optimally aligned subsets of l < k sequences to obtain an improved performance guarantee. For arbitrary I < k, we devise deterministic and randomized algorithms yielding performance guarantees of 2 - l/k. For fixed I, the running times of these algorithms are polynomial in n and k.
暂无评论