Towards formal specification of a distributed computing system

Onboard spacecraft computing system is a case of a functionally distributed system that requires continuous interaction among the nodes to control the operations at different nodes. A simple and reliable protocol is desired for such an application. This paper discusses a formal approach to specify the computing system with respect to some important issues encountered in the design and development of a protocol for the onboard distributed system. The issues considered in this paper are concurrency, exclusiveness and sequencing relationships among the various processes at different nodes. A 6-tuple model is developed for the precise specification of the system. The model also enables us to check the consistency of specification and deadlock caused due to improper specification. An example is given to illustrate the use of the proposed methodology for a typical spacecraft configuration. Although the theory is motivated by a specific application the same may be applied to other distributed computing system such as those encountered in process control industries, power plant control and other similar environments.

A knowledge-based clustering scheme

In this paper the notion of conceptual cohesiveness is precised and used to group objects semantically, based on a knowledge structure called ‘cohesion forest’. A set of axioms is proposed which should be satisfied to make the generated clusters meaningful.

Acyclic Edge Coloring of Graphs with Maximum Degree 4

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a'(G) <= Delta+2, where Delta=Delta(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Delta(G)<= 4, with the additional restriction that m <= 2n-1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m <= 2n, when Delta(G)<= 4. It follows that for any graph G if Delta(G)<= 4, then a'(G) <= 7.

Enhancing human action recognition with region proposals

Deep convolutional network models have dominated recent work in human action recognition as well as image classification. However, these methods are often unduly influenced by the image background, learning and exploiting the presence of cues in typical computer vision datasets. For unbiased robotics applications, the degree of variation and novelty in action backgrounds is far greater than in computer vision datasets. To address this challenge, we propose an “action region proposal” method that, informed by optical flow, extracts image regions likely to contain actions for input into the network both during training and testing. In a range of experiments, we demonstrate that manually segmenting the background is not enough; but through active action region proposals during training and testing, state-of-the-art or better performance can be achieved on individual spatial and temporal video components. Finally, we show by focusing attention through action region proposals, we can further improve upon the existing state-of-the-art in spatio-temporally fused action recognition performance.

A novel approach to 6-DOF adaptive trajectory tracking control of an AUV in the presence of parameter uncertainties

In this paper, the trajectory tracking control of an autonomous underwater vehicle (AUVs) in six-degrees-of-freedom (6-DOFs) is addressed. It is assumed that the system parameters are unknown and the vehicle is underactuated. An adaptive controller is proposed, based on Lyapunov׳s direct method and the back-stepping technique, which interestingly guarantees robustness against parameter uncertainties. The desired trajectory can be any sufficiently smooth bounded curve parameterized by time even if consist of straight line. In contrast with the majority of research in this field, the likelihood of actuators׳ saturation is considered and another adaptive controller is designed to overcome this problem, in which control signals are bounded using saturation functions. The nonlinear adaptive control scheme yields asymptotic convergence of the vehicle to the reference trajectory, in the presence of parametric uncertainties. The stability of the presented control laws is proved in the sense of Lyapunov theory and Barbalat׳s lemma. Efficiency of presented controller using saturation functions is verified through comparing numerical simulations of both controllers.

A multi-microprocessor architecture for solving partial differential equations

This paper presents the architecture of a fault-tolerant, special-purpose multi-microprocessor system for solving Partial Differential Equations (PDEs). The modular nature of the architecture allows the use of hundreds of Processing Elements (PEs) for high throughput. Its performance is evaluated by both analytical and simulation methods. The results indicate that the system can achieve high operation rates and is not sensitive to inter-processor communication delay.

Salan: A microprocessor-based medium speed experimental local area network

In this paper the implementation and application of a microprocessor-based medium speed experimental local area network using a coaxial cable transmission medium are dealt with. A separate unidirectional control wire has been used in order to provide a collision-free and fair medium access arbitration. As an application of the network, the design of a packet voice communication system is discussed.

Comment: Eigenvalue sensitivity method for optimal stabilisation of linear systems

In a letter RauA proposed a new method for designing statefeedback controllers using eigenvalue sensitivity matrices. However, there appears to be a conceptual mistake in the procedure, or else it is unduly restricted in its applicability. In particular the equation — BR~lBTK = A/.I, in which K is a positive-definite symmetric matrix.

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Revised benefits and costs of eradicating the red imported fire ant

The paper revisits estimates of cost/benefit for eradication in Australia provided in 2001 which were based largely on information about a US ecosystem. The study had two major components; spread modelling using a cellular automation model provided by Joe Scanlan and an impact analysis undertaken by the remaining authors. The revised figures provided in this study increased the damage estimate from $2.8 billion to $45 billion and the benefit-cost ratio of eradication efforts improved from 25:1 to 390:1.

Syntactic Approach to ECG Rhythm Analysis

A diagnostic system for ECG rhythm monitoring based on syntactic approaches to pattern recognition is presented here. The method proposed exploits the difference in shape and structure between arrhythmic and normal ECG patterns to generate distinctly different descriptions in terms of a chosen set of primitives. A given frame of signal is first approximated piecewise linearly into a set of line segments which are completely specified in terms of their length and slope values. The slope values are quantized into seven distinct levels and a unit-length line segment with a slope value in each of these levels is coded as a slope symbol. Seven such slope symbols constitute the set of primitives. The given signal is represented as a string of such symbols based on the length and angle of the line segments approximating the signal. Context-free languages are used for describing the classes of abnormal and normal ECG patterns considered here. Analysis of actual ECG data shows efficiency comparable with that of existing methods and a saving in processing time.

Pole placement in multi-input systems via elementary transformations

This paper is concerned with the development of an algorithm for pole placement in multi-input dynamic systems. The algorithm which uses a series of elementary transformations is believed to be simpler, computationally more efficient and numerically stable when compared with earlier methods. In this paper two methods have been presented.

New approach to improved detection and tracking performance in track-while-scan radars. Part 1: Introduction and review

The paper presents a new approach to improve the detection and tracking performance of a track-while-scan (TWS) radar. The contribution consists of three parts. In Part 1 the scope of various papers in this field is reviewed. In Part 2, a new approach for integrating the detection and tracking functions is presented. It shows how a priori information from the TWS computer can be used to improve detection. A new multitarget tracking algorithm has also been developed. It is specifically oriented towards solving the combinatorial problems in multitarget tracking. In Part 3, analytical derivations are presented for quantitatively assessing, a priori, the performance of a track-while-scan radar system (true track initiation, false track initiation, true track continuation and false track deletion characteristics). Simulation results are also shown.

New approach to improved detection and tracking performance in track-while-scan radars. Part 3: Performance prediction, optimisation and testing

The paper presents, in three parts, a new approach to improve the detection and tracking performance of a track-while-scan radar. Part 1 presents a review of the current status of the subject. Part 2 details the new approach. It shows how a priori information provided by the tracker can be used to improve detection. It also presents a new multitarget tracking algorithm. In the present Part, analytical derivations are presented for assessing, a priori, the performance of the TWS radar system. True track initiation, false track initiation, true track continuation and false track deletion characteristics have been studied. It indicates how the various thresholds can be chosen by the designer to optimise performance. Simulation results are also presented.