Search

Section 2 generalizes some concepts in directed graphs to configurations, called bigraph, which have directed as well as undirected lines. Several relations are defined in terms of a bigraph. Conditions are found under which it is possible to find weak, partial, and simple orders as well as preference relations. An application of this theory is found in following sections 3 and 4. These sections deal with the estimation of an order relation from paired comparisons in which ties may occur. (Author)

This paper presents new results from a study of flow-of-control in programs involving concurrent processes. Within the framework of flow-of-control, this paper:1) defines a property of parallel program behavior called proper termination (PT);2) shows that any properly terminating program containing a specification of the resources it requires will be free of deadlock;3) identifies other important features of PT programs; and4) presents an algorithm to rapidly decide PT for a given program.This work is presented in the context of the control-flow component of a complex bigraph (complex bi-logic directed graph) model of computation [1,10].

Bigraphs are a framework in which both existing process calculi and new models of behaviour can be formulated, yielding theory that is shared among these models. A short survey of the main features of bigraphs is presented, showing how they can be developed from standard graph theory using elementary category theory. The algebraic manipulation of bigraphs is outlined with the help of illustrations. The treatment of dynamics is then summarised. Finally, origins and some related work are discussed. The paper provides a motivating introduction to bigraphs.

Process calculi with various signatures and reaction rules may provide a theoretical basis for pervasive computing.

The possibilities for circuits of length 4 to appear together in a cubic bigraph are classified. That has consequences on the structure of minimally 1-factorable regular bigraphs, i.e. those in which each 1-factor lies in precisely one 1-factorization. We characterize minimally 1-factorable cubic bigraphs of girth 4.

We present a refinement, suggested by Jensen and Milner under the term kind, of pure bigraphs. We name the result kind bigraphs. This refinement generalises the notion of atomic and non-atomic controls, allowing a control to contain a subset of the set of controls.We show that this variation has relative pushouts and classify its idem pushouts. A canonical labelled transition system can be derived from this classification and we use known results to reason about bisimilarity on this transition system. We show how kind bigraphs can be used to describe Milner's homomorphic sortings and finally discuss the extra expressivity that parametric kind reaction rules allow.

We study the minimum number of complete bipartite subgraphs needed to cover and partition the edges of a k-regular bigraph on 2n vertices. Bounds are determined on the minima of these numbers for fixed n and k. Exact values of the minima are found for all n and k ≤ 4. The same results hold for directed graphs. Equivalently, we have determined bounds on the minimum value of the Boolean and nonnegative integer ranks of binary n × n matrices with constant row and column sum k for fixed n and k, obtaining the exact values of the minimum for k ≤ 4.

Bigraphical Reactive Systems (BRS) were designed by Milner as a universal formalism for modelling systems that evolve in time, locality, co-locality and connectivity. But the underlying model of location (the place graph) is a forest, which means there is no straightforward representation of locations that can overlap or intersect. This occurs in many domains, for example in wireless signalling, social interactions and audio communications. Here, we define bigraphs with sharing, which solves this problem by an extension of the basic formalism: we define the place graph as a directed acyclic graph, thus allowing a natural representation of overlapping or intersecting locations. We give a complete presentation of the theory of bigraphs with sharing, including a categorical semantics, algebraic properties, and several essential procedures for computation: bigraph with sharing matching, a SAT encoding of matching, and checking a fragment of the logic BiLog. We show that matching is an instance of the NP-complete sub-graph isomorphism problem and our approach based on a SAT encoding is also efficient for standard bigraphs. We give an overview of BigraphER (Bigraph Evaluator & Rewriting), an efficient implementation of bigraphs with sharing that provides manipulation, simulation and visualisation. The matching engine is based on the SAT encoding of the matching algorithm. Examples from the 802.11 CSMA/CA RTS/CTS protocol and a network management support system illustrate the applicability of the new theory.

Home wireless networks are difficult to manage and comprehend because of evolving locality, co-locality, connectivity and interaction. We define formal models of home wireless network infrastructure and policies and investigate how they can be used in a network management system designed to provide user-oriented support. We model spatial and temporal behaviour of network interactions and user-initiated network policies and define an online framework for generation of models from network and user-initiated events. The models are expressed in an extension to Milnerʼs bigraphical reactive systems. Analysis of the models is carried out in real-time by a bespoke bigraph reasoning system based on checking predicates, which is encoded as bigraph matching. Real-time model generation and analysis is implemented on the experimental Homework system router and trialled with synthetic and actual network data.

Human activity recognition in videos is important for content-based videos indexing, intelligent monitoring, human-machine interaction, and virtual reality. This paper uses the low-level feature-based framework for human activity recognition which includes feature extraction and descriptor computing, early multi-feature fusion, video representation, and classification. This paper improves the first two steps. We propose a spatio-temporal bigraph-based multi-feature fusion algorithm to capture the useful visual information for recognition. Meanwhile, we introduce a compressed spatio-temporal video representation to bag of words representation. Our experiments on two popular datasets show efficient performance.

We study the construction of labelled transition systems from reactive systems defined over directed bigraphs, a computational meta-model which subsumes other variants of bigraphs. First we consider wide transition systems whose labels are all those generated by the IPO construction; the corresponding bisimulation is always a congruence. Then, we show that these LTSs can be simplified further by restricting to a subclass of labels, which can be characterized syntactically. We apply this theory to the Fusion calculus: we give an encoding of Fusion in directed bigraphs, and describe its simplified wide transition system and corresponding bisimulation.

We give a short, elementary proof that the interval bigraphs are a strict subclass of the unit grid intersection graphs.

Background Microarray technology has made it possible to simultaneously monitor the expression levels of thousands of genes in a single experiment. However, the large number of genes greatly increases the challenges of analyzing, comprehending and interpreting the resulting mass of data. Selecting a subset of important genes is inevitable to address the challenge. Gene selection has been investigated extensively over the last decade. Most selection procedures, however, are not sufficient for accurate inference of underlying biology, because biological significance does not necessarily have to be statistically significant. Additional biological knowledge needs to be integrated into the gene selection procedure. Results We propose a general framework for gene ranking. We construct a bipartite graph from the Gene Ontology (GO) and gene expression data. The graph describes the relationship between genes and their associated molecular functions. Under a species condition, edge weights of the graph are assigned to be gene expression level. Such a graph provides a mathematical means to represent both species-independent and species-dependent biological information. We also develop a new ranking algorithm to analyze the weighted graph via a kernelized spatial depth (KSD) approach. Consequently, the importance of gene and molecular function can be simultaneously ranked by a real-valued measure, KSD, which incorporates the global and local structure of the graph. Over-expressed and under-regulated genes also can be separately ranked. Conclusion The gene-function bigraph integrates molecular function annotations into gene expression data. The relevance of genes is described in the graph (through a common function). The proposed method provides an exploratory framework for gene data analysis.