Crash failure detection in asynchronous agent communication languages

Agent Communication Languages (ACLs) have been developed to provide a way for agents to communicate with each other supporting cooperation in Multi-Agent Systems (MAS). In the past few years many ACLs have been proposed for MAS and new standards are emerging such as the ACL developed by the Foundation for Intelligent Physical Agents (FIPA). Despite these efforts, an important issue in the research on ACLs is still open and concerns how these languages should deal with failures of agents in asynchronous MAS. The Fault Tolerant Agent Communication Language ( - ) presented in this paper addresses this issue dealing with crash failures of agents. - provides high-level communication primitives which support a fault-tolerant anonymous interaction protocol designed for open MAS. We present a formal semantics for - and a formal specification of the underlying agent architecture. This formal framework allows us to prove that the ACL satisfies a set of well defined knowledge-level programming requirements. To illustrate the language features we show how - can be effectively used to write high-level executable specifications of fault tolerant protocols, such as the Contract Net one.     

Complexity of some arithmetic problems for binary polynomials

We study various combinatorial complexity measures of Boolean functions related to some natural arithmetic problems about binary polynomials, that is, polynomials over . In particular, we consider the Boolean function deciding whether a given polynomial over is squarefree. We obtain an exponential lower bound on the size of a decision tree for this function, and derive an asymptotic formula, having a linear main term, for its average sensitivity. This allows us to estimate other complexity characteristics such as the formula size, the average decision tree depth and the degrees of exact and approximative polynomial representations of this function. Finally, using a different method, we show that testing squarefreeness and irreducibility of polynomials over cannot be done in for any odd prime p. Similar results are obtained for deciding coprimality of two polynomials over as well.     

Cardinal interpolation with periodic polysplines on strips

Abstract  We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we prove the existence of a unique function in , polyharmonic of order p on each strip , , and periodic in its last n variables, whose restriction to the parallel hyperplanes , , coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in . The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal -splines. Keywords: cardinal -splines, polyharmonic functions, multivariable interpolation Mathematics Subject Classification (2000): 41A05, 41A15, 41A63     

Quantum Orlicz Spaces in Information Geometry

Let H₀ be a selfadjoint operator such that Tr is of trace class for some , and let denote the set of ε-bounded forms, i.e., for some 0 $$" align="middle" border="0"> . Let χ := Span . Let denote the underlying set of the quantum information manifold of states of the form . We show that if Tr ,

Image Approximation by Rectangular Wavelet Transform

We study image approximation by a separable wavelet basis and ϕ,ψ are elements of a standard biorthogonal wavelet basis in L₂(ℝ). Because k₁≠ k₂, the supports of the basis elements are rectangles, and the corresponding transform is known as the rectangular wavelet transform. We provide a self-contained proof that if one-dimensional wavelet basis has M dual vanishing moments then the rate of approximation by N coefficients of rectangular wavelet transform is for functions with mixed derivative of order M in each direction. These results are consistent with optimal approximation rates for such functions. The square wavelet transform yields the approximation rate is for functions with all derivatives of the total order M. Thus, the rectangular wavelet transform can outperform the square one if an image has a mixed derivative. We provide experimental comparison of image approximation which shows that rectangular wavelet transform outperform the square one. Vyacheslav Zavadsky got his M.Sc. (with distinction) in computer science and applied mathematics from Belarusian State University in 1994 and his Ph.D. in mathematics and statistics in 1998 from Belarusian Academy of Sciences and Belarusian State University. He worked at Institute of Mathematics of Belarusian Academy of sciences, and Belarusian center for medical technologies. He also held progressively responsible technical and research positions in the industry: at MZOR, eBusiness technologies, and Webmotion. At present, he is the principal software architect with Semiconductor insights. His research interests include mathematical and statistical methods in vision; machine learning, and structural data mining. Vyacheslav is author of more then ten peer reviewed papers and conference presentation, and 7 pending inventions.     

Deriving escape analysis by abstract interpretation

Escape analysis of object-oriented languages approximates the set of objects which do not escape from a given context. If we take a method as context, the non-escaping objects can be allocated on its activation stack; if we take a thread, Java synchronisation locks on such objects are not needed. In this paper, we formalise a basic escape domain as an abstract interpretation of concrete states, which we then refine into an abstract domain which is more concrete than and, hence, leads to a more precise escape analysis than . We provide optimality results for both and , in the form of Galois insertions from the concrete to the abstract domains and of optimal abstract operations. The Galois insertion property is obtained by restricting the abstract domains to those elements which do not contain garbage, by using an abstract garbage collector. Our implementation of is hence an implementation of a formally correct escape analyser, able to detect the stack allocatable creation points of Java (bytecode) applications.     

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.     

A Time-Splitting Spectral Method for the Generalized Zakharov System in Multi-Dimensions

The generalized Zakharov system (ZS) couples a dispersive field E (scalar or vectorial) and nondispersive fields with a propagating speed of . In this paper, we extend our one-dimensional time-splitting spectral method (TSSP) for the generalized ZS into higher dimension. A main new idea is to reformulate the multi-dimensional wave equations for the nondispersive fields into a first-order system using a change of variable defined in the Fourier space. The proposed scheme TSSP is unconditionally stable, second-order in time and spectrally accurate in space. Moreover, in the subsonic regime, it allows numerical capturing of the subsonic limit without resolving the small parameters . Numerical examples confirm these properties of this method     

Linear Interval Equations: Midpoint Preconditioning May Produce a 100% Overestimation for Arbitrarily Narrow Data Even in Case <Emphasis Type="Italic">n</Emphasis> = 4

We construct a linear interval system Ax = b with a 4 × 4 interval matrix whose all proper interval coefficients (there are also some noninterval ones) are of the form [–, ]. It is proved that for each > 0, the interval hull and interval hull of the midpoint preconditioned system satisfy and , hence midpoint preconditioning produces a 100% overestimation of independently of in this case. The example was obtained as a result of an extensive MATLAB search.     

Coupling and self-stabilization

A randomized self-stabilizing algorithm is an algorithm that, whatever the initial configuration is, reaches a set of М legal configurations} in finite time with probability 1. The proof of convergence towards is generally done by exhibiting a potential function , which measures the “vertical” distance of any configuration to , such that decreases with non-null probability at each step of . We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance between any pair of configurations, such that decreases in expectation at each step of . In contrast with classical methods, our coupling method does not require the knowledge of . In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs.     

Two-Parameter Discrete Systems over a Residue Ring and Their Properties

A class of two-parameter discrete systems defined on the ring of class of residues of integers modulo m is studied. All solutions are shown to be periodic, stability conditions (equality of solutions to zero, beginning from a certain instant) and a controllability condition are formulated. Controllability is shown to guarantee stabilizability.