Randomized mutual exclusion on a multiple access channel

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes execute a concurrent program that occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource (also called a critical section), in such a way that at any time, there is at most one process accessing it. In our considerations, the shared resource is the shared communication channel itself (multiple access channel), and the main challenge arises because the channel is also the only mean of communication between these processes. We consider both the classic and a slightly weaker version of mutual exclusion, called \(\varepsilon \)-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most \(\varepsilon \). We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while the \(\varepsilon \)-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker \(\varepsilon \)-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

A Rough Set Approach to Estimating the Game Value and the Shapley Value from Data

A value of a game v is a function which to each coalition S assigns the value v(S) of this coalition, meaning the expected pay–off for players in that coalition. A classical approach of von Neumann and Morgenstern [6] had set some formal requirements on v which contemporary theories of value adhere to. A Shapley value of the game with a value v [14] is a functional Φ giving for each player p the value Φ_p(v) estimating the expected pay-off of the player p in the game. Game as well as conflict theory have been given recently much attention on the part of rough and fuzzy set communities [11,8,1,4,7,2]. In particular, problems of plausible strategies [1] in conflicts as well as problems related to Shapley's value [3,2] have been addressed.We confront here the problem of estimating a value as well as Shapley's value of a game from a partial data about the game. We apply to this end the rough set ideas of approximations, defining the lower and the upper value of the game and, respectively, the lower and upper Shapley value. We also define a notion of an exact coalition, on which both values coincide giving the true value of the game; we investigate the structure of the family of exact sets showing its closeness on complements, disjoint sums, and intersections of coalitions covering the set of players. This work sets open a new area of rough set applications in mining constructs from data. The construct mined in this case are values as well as Shapley values of games.     

Kernel orthonormalization in radial basis function neural networks

This paper deals with optimization of the computations involved in training radial basis function (RBF) neural networks. The main contribution of the reported work is the method for network weights calculation, in which the key idea is to transform the RBF kernels into an orthonormal set of functions (using the standard Gram-Schmidt orthogonalization). This significantly reduces the computing time if the RBF training scheme, which relies on adding one kernel hidden node at a time to improve network performance, is adopted. Another property of the method is that, after the RBF network weights are computed, the original network structure can be restored back. An additional strength of the method is the possibility to decompose the proposed computing task into a number of parallel subtasks so gaining further savings on computing time. Also, the proposed weight calculation technique has low storage requirements. These features make the method very attractive for hardware implementation. The paper presents a detailed derivation of the proposed network weights calculation procedure and demonstrates its validity for RBF network training on a number of data classification and function approximation problems.     

Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997     

A General Framework for Trajectory Triangulation

The multiple view geometry of static scenes is now well understood. Recently attention was turned to dynamic scenes where scene points may move while the cameras move. The triangulation of linear trajectories is now well handled. The case of quadratic trajectories also received some attention. We present a complete generalization and address the problem of general trajectory triangulation of moving points from non-synchronized cameras. Two cases are considered: (i) the motion is captured in the images by tracking the moving point itself, (ii) the tangents of the motion only are extracted from the images. The first case is based on a new representation (to computer vision) of curves (trajectories) where a curve is represented by a family of hypersurfaces in the projective space ?⁵. The second case is handled by considering the dual curve of the curve generated by the trajectory. In both cases these representations of curves allow: (i) the triangulation of the trajectory of a moving point from non-synchronized sequences, (ii) the recovery of more standard representation of the whole trajectory, (iii) the computations of the set of positions of the moving point at each time instant an image was made. Furthermore, theoretical considerations lead to a general theorem stipulating how many independent constraints a camera provides on the motion of the point. This number of constraint is a function of the camera motion. On the computation front, in both cases the triangulation leads to equations where the unknowns appear linearly. Therefore the problem reduces to estimate a high-dimensional parameter in presence of heteroscedastic noise. Several method are tested.     

Mo–Si–B alloys for ultra-high-temperature space and ground applications: liquid-assisted fabrication under various temperature and time conditions

Journal of Materials Science - Boron-doped molybdenum silicides have been already recognized as attractive candidates for space and ground ultra-high-temperature applications far beyond limits of...     

Intercomparison of a portable and two stationary mobility particle sizers for nanoscale aerosol measurements

During occupational exposure studies, the use of conventional scanning mobility particle sizers (SMPS) provides high quality data but may convey transport and application limitations. New instruments aiming to overcome these limitations are being currently developed. The purpose of the present study was to compare the performance of the novel portable NanoScan SMPS TSI 3910 with that of two stationary SMPS instruments and one ultrafine condensation particle counter (UCPC) in a controlled atmosphere and for different particle types and concentrations.

The results show that NanoScan tends to overestimate particle number concentrations with regard to the UCPC, particularly for agglomerated particles (ZnO, spark generated soot and diesel soot particles) with relative differences >20%. The best agreements between the internal reference values and measured number concentrations were obtained when measuring compact and spherical particles (NaCl and DEHS particles). With regard to particle diameter (modal size), results from NanoScan were comparable < [± 20%] to those measured by SMPSs for most of the aerosols measured.

The findings of this study show that mobility particle sizers using unipolar and bipolar charging may be affected differently by particle size, morphologies, particle composition and concentration. While the sizing accuracy of the NanoScan SMPS was mostly within ±25%, it may miscount total particle number concentration by more than 50% (especially for agglomerated particles), thus making it unsuitable for occupational exposure assessments where high degree of accuracy is required (e.g., in tier 3). However, can be a useful instrument to obtain an estimate of the aerosol size distribution in indoor and workplace air, e.g., in tier 2.