Split-Freedom And Mvd-Intersection - A New Characterization Of Multivalued Dependencies Having Conflict-Free Covers

Sets of multivalued dependencies (MVDs) having conflict-free covers are important to the theory and design of relational databases [2,12,15,16]. Their desirable properties motivate the problem of testing a set M of MVDs for the existence of a confiict-free cover. In [8] Goodman and Tay have proposed an approach based on the possible equivalence of M to a single (acyclic) join dependency (JD). We remark that their characterization does not lend an insight into the nature of such sets of MVDs. Here, we use notions that are intrinsic to MVDs to develop a new characterization. Our approach proceeds in two stages. In the first stage, we use the notion of “split-free” sets of MVDs and obtain a characterization of sets M of MVDs having split-free covers. In the second, we use the notion of “intersection” of MVDs to arrive at a necessary and sufficient condition for a split-free set of MVDs to be conflict-free. Based on our characterizations, we also give polynomial-time algorithms for testing whether M has split-free and conflict-free covers. The highlight of our approach is the clear insight it provides into the nature of sets of MVDs having conflict-free covers. Less emphasis is given in this paper to the actual efficiency of the algorthms. Finally, as a bonus, we derive a desirable property of split-free sets of MVDs,thereby showing that they are interesting in their own right.

Distributed Robotic Vision as a service

The vision sense of standalone robots is limited by line of sight and onboard camera capabilities, but processing video from remote cameras puts a high computational burden on robots. This paper describes the Distributed Robotic Vision Service, DRVS, which implements an on-demand distributed visual object detection service. Robots specify visual information requirements in terms of regions of interest and object detection algorithms. DRVS dynamically distributes the object detection computation to remote vision systems with processing capabilities, and the robots receive high-level object detection information. DRVS relieves robots of managing sensor discovery and reduces data transmission compared to image sharing models of distributed vision. Navigating a sensorless robot from remote vision systems is demonstrated in simulation as a proof of concept.

Reflexive Incidence Matrx (RIM) Representation of Petr Nets

Although incidence matrix representation has been used to analyze the Petri net based models of a system, it has the limitation that it does not preserve reflexive properties (i.e., the presence of selfloops) of Petri nets. But in many practical applications self-loops play very important roles. This paper proposes a new representation scheme for general Petri nets. This scheme defines a matrix called "reflexive incidence matrix (RIM) c which is a combination of two matrices, a "base matrix Cb,,, and a "power matrix CP." This scheme preserves the reflexive and other properties of the Petri nets. Through a detailed analysis it is shown that the proposed scheme requires less memory space and less processing time for answering commonly encountered net queries compared to other schemes. Algorithms to generate the RIM from the given net description and to decompose RIM into input and output function matrices are also given. The proposed Petri net representation scheme is very useful to model and analyze the systems having shared resources, chemical processes, network protocols, etc., and to evaluate the performance of asynchronous concurrent systems.

Aircraft pursuit-evasion problems with variable speeds

Aircraft pursuit-evasion encounters in a plane with variable speeds are analysed as a differential game. An engagement-dependent coordinate system confers open-loop optimality on the game. Each aircraft's optimal motion can be represented by extremel trajectory maps which are independent of role, adversary and capture radius. These maps are used in two different ways to construct the feedback solution. Some examples are given to illustrate these features. The paper draws on earlier results and surveys several existing papers on the subject.

A Microprocessor-Based Pulse-Height Analyzer

Need to analyze particles in a flow? This system takes electrical pulses from acoustical or optical sensors and groups them into bands representing ranges of particle sizes.

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.