Search

There exist several approaches proposed for building Context-Aware Systems (CAS). However, due to the continually changing environment, the large number of interrelated components, complexity and diversity of application domains make the modelling of context-aware systems a particularly challenging task. To address the increasing complexity of the modelling: i) It is critical to take into account the importance of the environment (operational context); and ii) rely on software engineering concepts such as abstraction and modularity in order to reduce the level of complexity. Also, a context-aware system may require intelligence and autonomy. These naturally lead us to apply intelligent agent-based engineering. This work introduces a formal layered design approach that combines intelligent control of multi-agent systems and bigraph's rigor to model context-aware systems. Bigraphical reactive systems are particularly compelling for their capacity to specify, simultaneously, the physical and logical distribution of system components and their interconnections using two distinct structures; that is: place graph and link graph. While the behaviour and dynamic evolution are expressed using defined reaction rules, and as a last step, the bigraph specifications are coded in the Maude language to allow their execution and the verification of their validity.

Subgraph matching finds all embeddings from a data graph that are identical to a query graph. Recent algorithms work by generating a tree-structured index on the data graph based on the query graph, ordering the vertices root-to-leaf path-by-path in the tree, and enumerating the embeddings following the matching order. However, we find such path-based ordering and tree-structured index based enumeration inherently limit the performance due to the lack of consideration on the edges among the vertices across tree paths. To address this problem, we propose an approach that generates the matching order based on a cost model considering both the edges among query vertices and the number of candidates. Furthermore, we create a bigraph index for candidate vertices and their selected neighbors in the data graph, and use this index to perform enumeration along the matching order. Our experiments on both real-world and synthetic datasets show that our method outperforms the state of the art by orders of magnitude.

In this paper, we present a process calculus called BigrTiMo that combines the rTiMo calculus and the Bigraph model. BigrTiMo calculus is capable of specifying a rich variety of properties for structure-aware mobile systems. Compared with rTiMo, our BigrTiMo calculus can specify not only time, mobility and local communication, but also remote communication. We then investigate the operational semantics of the BigrTiMo calculus and develop an executable formal specification of our BigrTiMo calculus in a declarative language called Maude. In addition, we verify safety properties and liveness properties of the mobile systems described by BigrTiMo using state exploration and LTL model checking in Maude. Based on Hoare and He's Unifying Theories of Programming (UTP), we study the semantic foundation of this highly expressive modelling language and propose a denotational semantic model and a set of algebraic laws for it. The semantic model in this paper covers time, location, communication and global shared variable at the same time. We also demonstrate the proofs of some algebraic laws based on our denotational semantics. Moreover, we explore how the algebraic semantics relates with the operational semantics and denotational semantics, which is conducted by the study of deriving the operational semantics and denotational semantics from algebraic semantics. We prove the equivalence between the derived transition system (e.g., the operational semantics) and the derivation strategy, which indicates that the operational semantics is sound and complete.

We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done ...

Software system evolution is an active and important research topic in software engineering. In guiding software system evolution, software architecture plays a critical role. In the traditional software architecture, only the link information of components is considered, while the place information of components is usually neglected. However, due to the emerging mobile computing, pervasive computing, and intelligent computing, the place information is as important as the link information in the software architecture. Especially in mobile computing environments, the place changes often lead to changes in software configuration and functionality. In this paper, we study the Bigraph specification of software architecture and use it to describe both link and place information in detail. Based on Bigraph specification, we investigate the structural characteristics in the software architecture, and design checking algorithms for the component’s link exceptions and place exceptions. Furthermore, we address the well-evolved software architecture from a new perspective, which includes three basic evolution operation rules and their well-evolved conditions. We discuss the overall software architecture evolution through strong and weak bi-simulation in terms of software functionality. Finally, two case studies about software system in the evolution operation are presented, which illustrate the effectiveness of our approach.

The biclique graph K B ( G ) is the intersection graph of all the bicliques of a graph G . The aim of our work is to recognize graphs that are biclique graphs of interval bigraphs ( IBG ). In this paper we prove that K B ( IBG ) ⊂ K 1 , 4 -free co-comparability graphs. We also study the class of biclique graphs of proper interval bigraphs ( PIB ). Recall that PIB is equal to the class of bipartite permutation graphs ( BPG ). We present a characterization of the class K B ( PIB ) and of the biclique graphs of a subclass of PIB that leads to a polynomial time recognition algorithm. We also present characterizations of biclique graphs of some classes such as complete graphs, trees and graphs with girth at least 5.

Directed bigraphs are a meta-model which generalises Milner’s bigraphs by taking into account the request flow between controls and names. A key problem about these bigraphs is that of bigraph embedding, i.e., finding the embeddings of a bigraph inside a larger one. We present an algorithm for computing embeddings of directed bigraphs, via a reduction to a constraint satisfaction problem. We prove soundness and completeness of this algorithm, and provide an implementation in jLibBig, a general Java library for manipulating bigraphical reactive systems, together with some experimental results.

Incidence coalgebras of categories in the sense of Joni and Rota are studied, specifically cases where a monoidal product on the category turns these into (weak) bialgebras. The overlap with the theory of combinatorial Hopf algebras and that of Hopf quivers is discussed, and examples including trees, skew shapes, Milner’s bigraphs and crossed modules are considered.

Bigraphen wurden von Robin Milner als grundlegende Theorie und Modellierungsformalismus f��r Strukturen im Ubiquitous Computing vorgeschlagen, wobei Bigraphische Reactive Systeme (BRS) das dynamische Verhalten erfassen. Ein BRS beschreibt, auf welche Arten sich eine Struktur durch Anwendung von Transformationsregeln ��� Reaktionsregeln ���entwickeln kann. Die Reaktionsregeln machen es m��glich, Teile von Bigraphen selektiv umzuschreiben. Bestehende Werkzeuge f��r bigraphisches Denken konzentrieren sich auf theoretische Aspekte, was ihre praktische Anwendung behindert. In dieser Arbeit stellen wir Werkzeuge vor, um bei Spezifikation zu helfen und das Problem vom Umschreiben in Bigraphen mit Graphoperationen anzugehen. Damit f��rdern wir eine (in Bezug auf die urspr��ngliche Theorie) einfachere, praxistaugliche Sicht auf Bigraphen. Das konkrete Ergebnis ist ein Forschungsprototyp, der auf Rapid-Prototyping-Einrichtungen f��r technische Anwendungen abzielt. Insbesondere f��hren wir die Unterst��tzung f��r Portvariablen mit lokalem G��ltigkeitsbereich in Reaktionen ein und bieten eine genaue Definition des Umschreibungsprozesses mit Graphoperationen inklusive Unterst��tzung von Roots, Sites und Ports. Wir evaluieren unseren Ansatz zur Spezifikation und schnellem Prototyping mittels eines herausfordernden Szenarios im Bereich von Edge-Computing., Bigraphs have been proposed by Robin Milner as a fundamental theory and modeling formalism for structures in ubiquitous computing, with Bigraphical Reactive Systems capturing dynamic behavior. A BRS describes possible ways with which a structure can evolve through application of transformation rules ���called reaction rules��� which selectively rewrite parts of a bigraph. Existing tool support for bigraphical reasoning focuses on theoretical aspects, thus hindering their adoption for engineering applications.In this thesis, we provide facilities to aid specification as well as tackle the rewriting problem in bigraphs with graph operations, promoting a simpler (with respect to theoriginal theory) view of bigraphs, suited for practical purposes. The concrete outcome isa research prototype that aims at rapid prototyping facilities for engineering applications.Specifically, we introduce support for locally-scoped port variables in reactions, and provide a precise definition of the rewriting process with graph operations including support for roots, sites and ports. We evaluate our approach to specification and rapid prototyping over a challenging scenario within edge computing.

Identifying all the right requirements is indispensable for the success of any system. These requirements need to be engineered with precision in the early phases. Principally, late corrections costs are estimated to be more than 200 times as much as corrections during requirements engineering (RE). Especially Big data area, it becomes more and more crucial due to its importance and characteristics. In fact, and after literature analyzing, we note that currents RE methods do not support the elicitation of Big data projects requirements. In this study, we propose the BiStar novel method as extension of iStar to under- take some Big data characteristics such as (volume, variety ...etc). As a first step, we identify some missing concepts that currents requirements engineering methods do not support. Next, BiStar, an extension of iStar is developed to take into account Big data specifics characteristics while dealing with require- ments. In order to ensure the integrity property of BiStar, formal proofs were made, we perform a bigraph based description on iStar and BiStar. Finally, an application is conducted on iStar and BiStar for the same illustrative scenario. The BiStar shows important results to be more suitable for eliciting Big data projects requirements. 22 03

Widespread access to low-cost, high computing power allows for increased computerization of everyday life. However, high-performance computers alone cannot meet the demands of systems such as the Internet of Things or multi-agent robotic systems. For this reason, modern design methods are needed to develop new and extend existing projects. Because of high interest in this subject, many methodologies for designing the aforementioned systems have been developed. None of them, however, can be considered the default one to which others are compared to. Any useful methodology must provide some tools, versatility, and capability to verify its results. This paper presents an algorithm for verifying the correctness of multi-agent systems modeled as tracking bigraphical reactive systems and checking whether a behavior policy for the agents meets non-functional requirements. Memory complexity of methods used to construct behavior policies is also discussed, and a few ways to reduce it are proposed. Detailed examples of algorithm usage have been presented involving non-functional requirements regarding time and safety of behavior policy execution.

Context-aware computing refers to system ability to sense its environment and modify its behavior for delivering suitable services. Having such kind of systems with the Near Field Communication (NFC) capability, opens new perspectives and research areas, allowing very useful type of applications known as NFC-based context-aware applications. These systems require correctness due to their applicability and then need to be proven formally using exhaustive analysis approach such as formal verification. In literature, most of works focuses on creating a general model for context aware systems ignoring the specificity of certain applications such as NFC applications where they present a higher complexity. We emphasize the existence of little or no work in this area supporting formal modeling. To boost it, we propose BigNFC as a novel formal-model based on Bigraphical Reactive Systems (BRS) taking account the interaction mode from the beginning, so we establish mapping between BRS and BigNFC components, where the structures are modelled as bigraphs and behaviors as rewriting rules. Finally, to validate our model, we have applied it on a real-life application and some properties were checked successfully.

Background: The evidence-base of therapy studies for reading difficulties is notably sparse, particularly for individuals with deep dyslexia. Research using grapheme-to-phoneme correspondence appro...

The cyber-physical space is a spatial environment that integrates the cyber and physical worlds to provide an intelligent environment for users to conduct their day-to-day activities. Mobile users and mobile objects are ubiquitous in this space, thereby exerting tremendous pressure on its security model. This model must ensure that both cyber and physical objects are always handled securely in this dynamic environment. In this paper, we propose a systematic solution to be able to specify security policies of the cyber-physical space and ensure that security requirements hold in these policies. We first formulate a topology configuration model to capture the topology characteristics of the cyber and physical worlds. Then, based on this model, a Topology-Aware Cyber- Physical Access Control model (TA-CPAC) is proposed, which can ensure the security of the cyber and physical worlds at the same time by adjusting permission assignment dynamically. Then, the topology configuration and TA-CPAC models are formalized by bigraphs and Bigraph Reactive System (BRS), respectively, allowing us to use model checking to rationalize the consequences of the evolution of topological configurations on the satisfaction of security requirements. Finally, a case study on a building automation access control system is conducted to evaluate the effectiveness of the proposed approach.

Actor Networks are a modelling framework for cyber-physical-system protocols based on Latour's actor-network theory that addresses the way we now create and exploit the power of networks whose components are no longer limited to programs, but can also include humans and physical artefacts as actors. The main contribution of this paper is a logic for modelling and reasoning about such actor networks that results from a two-stage constrained-hybridisation process: the first stage corresponds to a logic that captures the structure of actor networks and the way knowledge or data flows across them; the second addresses their dynamic aspects, i.e., the way actor networks can evolve as a result of the interactions that occur within them. For each of these stages, we develop a sound and complete proof system, and we illustrate how the framework can be used for modelling and analysing properties of cyber-physical-system protocols. This two-stage constrained-hybridisation process advances the theoretical and practical aspects of hybrid logics by providing new insights and results that go beyond the specific domain of actor networks. On the other hand, and in line with Milner's bigraph paradigm, the paper also makes a novel contribution to the development of formal methods for systems where connectivity and locality play a fundamental role.

International audience; Elasticity property allows cloud systems to adapt to their input workload by provisioning and deprovisioning resources as the demand grows and drops. However, due to the unpredictable nature of workload, providing accurate action plans to manage a cloud system's elasticity is a particularly challenging task. In this study, the authors propose a bigraphical reactive system-based approach to provide a formal modelling of cloud systems’ structure using bigraphs, and their elastic behaviours using bigraphical reaction rules. They introduce elasticity strategies to describe cloud systems’ auto-adaptation behaviours. One step further, they encode the bigraphical specifications into Maude language to enable an autonomic executability of the elastic behaviours and verify their correctness. Finally, they propose a queuing-based approach to discuss and analyse elasticity strategies in cloud systems through different simulated scenarios.

The bigraph theory, devised by Robin Milner, is a recent mathematical framework for concurrent processes. Its generality is able to subsume many existing process calculi, for example, CCS, CSP, and Petri nets. Further, it provides a uniform proof of bisimilarity, which is a congruence. We present the first canonical string encoding for pure and lean bigraphs by lifting the breadth-first canonical form of rooted unordered trees to a unique representation for bigraphs up to isomorphism (i.e., lean-support equivalence). The encoding’s applicability is limited to atomic alphabets. The time complexity is $$O(n^{2}k\, d \log {d})$$ O ( n 2 k d log d ) , where n is the number of places, d the degree of the place graph and k the maximum arity of a bigraph’s signature. We provide proof of the correctness of our method and also conduct experimental measurements to assess the complexity.

Multi-agent systems are recognized as a major area of distributed artificial intelligence. In fact, MAS have found multiple applications, including the design and development of complex, hierarchical and critical systems. However, ensuring the accuracy of complex interactions and the correct execution of activities of a MAS is becoming a tedious task. In this work, we focus on the formal specification of interaction, holonic and sociotechnical concepts to the BRS-MAS model. The proposed approach, is based on Bigraphical reactive systems. Bigraphs, provide means to specify at same time locality and connectivity of different type of system ranging from soft systems to cyber physical systems. In addition, to its intuitive graphical representation, it provides algebraic definition. This, makes the resulted specifications more precise. Further, it enables the verification of the specified system at the design time (before the implementation) using verification tools.

Many real-world large datasets correspond to bipartite graph data settings—think for example of users rating movies or people visiting locations. Although there has been some prior work on data analysis with such bigraphs, no general network-oriented methodology has been proposed yet to perform node classification. In this paper we propose a three-stage classification framework that effectively deals with the typical very large size of such datasets. The stages are: (1) top node weighting, (2) projection to a weighted unigraph, and (3) application of a relational classifier. This paper has two major contributions. Firstly, this general framework allows us to explore the design space, by applying different choices at the three stages, introducing new alternatives and mixing-and-matching to create new techniques. We present an empirical study of the predictive and run-time performances for different combinations of functions in the three stages over a large collection of bipartite datasets with sizes of up to $$20\,\hbox {million} \times 30\,\hbox {million}$$ nodes. Secondly, thinking of classification on bigraph data in terms of the three-stage framework opens up the design space of possible solutions, where existing and novel functions can be mixed and matched, and tailored to the problem at hand. Indeed, in this work a novel, fast, accurate and comprehensible method emerges, called the SW-transformation, as one of the best-performing combinations in the empirical study.

Human-autonomy teaming (HAT) scenarios feature humans and autonomous agents collaborating to meet a shared goal. For effective collaboration, the agents must be transparent and able to share important information about their operation with human teammates. We address the challenge of transparency for Belief-Desire-Intention agents defined in the Conceptual Agent Notation (CAN) language. We extend the semantics to model agents that are observable (i.e. the internal state of tasks is available), and attention-directing (i.e. specific states can be flagged to users), and provide an executable semantics via an encoding in Milner's bigraphs. Using an example of unmanned aerial vehicles, the BigraphER tool, and PRISM, we show and verify how the extensions work in practice., Comment: In Proceedings FMAS 2021, arXiv:2110.11527

We propose a formal approach based on Bigraphical Reactive Systems (BRSs) and model checking techniques for modeling and verifying the interaction behaviours of SLA-based cloud computing systems. In the first phase of this approach, we address the modeling of the static structure and the dynamic behavior of cloud systems using BRSs. We show how bigraphs enable the description of the different cloud entities, including cloud actors, cloud services, Service Level Agreements (SLAs), the diversity of their properties, and the complex interactions and dependencies among them. Furthermore, we propose a four-stages SLA lifecycle, and define a set of bigraphical reaction rules to abstract these stages and model the dynamic nature of the cloud. The second phase of this approach verifies that the behavior of services and cloud actors will cope with the agreed SLA terms during the lifecycle of the SLA. We map the proposed bigraphical models into SMV descriptions. Then, we express the interaction behaviors as a set of liveness and safety properties using Linear Temporal Logic (LTL) and Computation Tree Logic (CTL) formulas, and we use the NuSMV model checker to verify them. Finally, we define a case study on which we illustrate the application of our proposed approach.

In this paper we develop a compositional vector-based semantics of positive transitive sentences in quantum natural language processing for a non-English language, i.e. Persian, to compare the parametrised quantum circuits of two synonymous sentences in two languages, English and Persian. By considering grammar+meaning of a transitive sentence, we translateDisCoCat diagram via ZX-calculus into quantum circuit form. Also, we use a bigraph method to rewrite DisCoCat diagram and turn into quantum circuit in the semantic side.

Describing spatio-temporal behaviors of cyber-physical systems attracts more and more attention in the filed of intelligent transportation systems and biological systems. The major problem is expressiveness and verifiability for modeling and analysis of spatio-temporal behaviors. In order to verify spatial and spatio-temporal behaviors, in this paper, we propose a methodology to model the evolution of spatial scene snapshots and verify the spatio-temporal models. Firstly, we define a novel Topograph through inducing Bigraph in topological space to characterize cyber-physical systems and verify the model against patterns specified with S4u formulas. Secondly, for spatio-temporal verification, we extend Topograph in dense time, named Temporal Topograph, to describe the evolution of spatial objects, which are verified against spatio-temporal specification language. We evaluate the applicability of the approach on CBTC-based intelligent transportation systems.

BigrTiMo [1], a process algebra that combines the rTiMo calculus [2] and the Bigraph model [3], is capable of specifying a rich variety of properties for structure-aware mobile systems. Compared with the rTiMo model, our BigrTiMo calculus can specify not only time, mobility and the local communication (the two communication components should be at the same location), but also the remote communication (the two communication components can be at the different locations). In this paper, we present an axiomatic approach to BigrTiMo program language verification based on Hoare-style [4] proof rules. In order to describe the timing of observable actions and the state of the bigraph, we extend the assertion language with primitives. Moreover, we prove the soundness of our proof rules and show the application of the proof rules via an example.

In modern cloud-based architectures, containers play a central role: they provide powerful isolation mechanisms such that developers can focus on the logic and dependencies of applications while system administrators can focus on deployment and management issue. In this work, we propose a formal model for container-based systems, using the framework of Bigraphical Reactive Systems (BRSs). We first introduce local directed bigraphs, a graph-based formalism which allows us to deal with localized resources. Then, we define a signature for modelling containers and provide some examples of bigraphs modelling containers. These graphs can be analysed and manipulated using techniques from graph theory: properties about containers can be formalized as properties of the corresponding bigraphic representations. Moreover, it turns out that the composition of containers as performed by e.g. docker-compose, corresponds precisely to the composition of the corresponding bigraphs inside an ``environment bigraph'' which in turn is obtained directly from the YAML file used to define the composition of containers.

Bigraphs and their algebra is a model of concurrency. Fuzzy bigraphs are a generalization of birgraphs intended to be a model of concurrency that incorporates vagueness. More specifically, this model assumes that agents are similar, communication is not perfect, and, in general, everything is or happens to some degree.

This paper is related to the problem of finding the maximal quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in the bigraph is its "almost" complete subgraph. The relaxation of completeness can be understood variously; here, we assume that the subgraph is a $\gamma$-quasi-biclique if it lacks a certain number of edges to form a biclique such that its density is at least $\gamma \in (0,1]$. For a bigraph and fixed $\gamma$, the problem of searching for the maximal quasi-biclique consists of finding a subset of vertices of the bigraph such that the induced subgraph is a quasi-biclique and its size is maximal for a given graph. Several models based on Mixed Integer Programming (MIP) to search for a quasi-biclique are proposed and tested for working efficiency. An alternative model inspired by biclustering is formulated and tested; this model simultaneously maximizes both the size of the quasi-biclique and its density, using the least-square criterion similar to the one exploited by triclustering \textsc{TriBox}.

A bipartite graph \(G=(U,V,E)\) is an interval bigraph if and only if there is a one to one correspondence between \(U \cup V\) and a family of intervals on the number line such that two vertices of opposing partite sets are neighbors precisely if their corresponding intervals intersect. Interval bigraphs, as well as many subclasses, have been extensively studied by multiple researchers along the years, and many results on their structural and computational properties have been discovered. A bipartite graph \(G=(U,V,E)\) is a circular arc bigraph if and only if there is a one to one correspondence between \(U \cup V\) and a family of arcs on a circle such that two vertices of opposing partite sets are neighbors precisely if their corresponding arcs intersect. While it is a generalization of interval bigraphs, it remains a relatively unexplored topic. Few studies about the class and its proper, unit and Helly subclasses have been presented. In this work, we study some subclasses of these classes. We provide forbidden structure characterizations for the Helly subclass of interval bigraphs, as well as the class of non-bichordal Helly circular arc bigraphs. We also prove that Helly interval bigraphs are a subclass of proper interval bigraphs, and that non-bichordal Helly circular arc bigraphs are a subclass of proper circular arc bigraphs.

One of the key features of Internet of Things (IoT) systems is self-adaptation. Modelling such systems efficiently requires minimizing the gap between system requirements and user requirements. Here an IoT System for Harbour Surveillance and Ferry Monitoring is considered as a case study. Modelling its behaviour and purpose is very essential before designing and deploying the system. Some of the modelling approaches such as AODB and Bigraphs are presented and explored here to evaluate how well they depict the aspects of the system. The mental model is designed to identify the functional interfaces of the Harbour Surveillance and Ferry Monitoring case study.

A hypergraph $\mathcal H$ is super-pancyclic if for each $A \subseteq V(\mathcal H)$ with $|A| \geq 3$, $\mathcal H$ contains a Berge cycle with base vertex set $A$. We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient for this. In particular, they are sufficient for every hypergraph $\mathcal H$ with $ \delta(\mathcal H)\geq \max\{|V(\mathcal H)|, \frac{|E(\mathcal H)|+10}{4}\}$. We also consider super-cyclic bipartite graphs: those are $(X,Y)$-bigraphs $G$ such that for each $A \subseteq X$ with $|A| \geq 3$, $G$ has a cycle $C_A$ such that $V(C_A)\cap X=A$. Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs., Comment: 17 pages

Complex problems can be sometimes solved efficiently via recursive decomposition strategies. In this line, the tree decomposition approach equips problems modelled as graphs with tree-like parsing structures. Following Milner’s flowgraph algebra, in a previous paper two of the authors introduced a strong network algebra to represent open graphs (up to isomorphism), so that homomorphic properties of open graphs can be computed via structural recursion. This paper extends this graphical-algebraic foundation to tree decomposable graphs. The correspondence is shown: (i) on the algebraic side by a loose network algebra, which relaxes the restriction reordering and scope extension axioms of the strong one; and (ii) on the graphical side by Milner’s binding bigraphs, and elementary tree decompositions. Conveniently, an interpreted loose algebra gives the evaluation complexity of each graph decomposition. As a key contribution, we apply our results to dynamic programming (DP). The initial statement of the problem is transformed into a term (this is the secondary optimisation problem of DP). Noting that when the scope extension axiom is applied to reduce the scope of the restriction, then also the complexity is reduced (or not changed), only so-called canonical terms (in the loose algebra) are considered. Then, the canonical term is evaluated obtaining a solution which is locally optimal for complexity. Finding a global optimum remains an NP-hard problem.

The end-vertex problem for a search algorithm asks whether a vertex of the input graph is the last visited vertex of an execution of that search algorithm. We consider the end-vertex problem restricted to AT-free bigraphs for various search algorithms: Breadth-First Search (BFS), Lexicographic Breadth-First Search (LBFS), Depth-First Search (DFS), and Maximal Neighbourhood Search (MNS). Deciding whether a vertex of a graph is the end-vertex of any of these search algorithms is NP-complete in general. We show that we can decide whether a vertex is an end-vertex of BFS or MNS in polynomial time on AT-free bigraphs. Additionally, we show that we can decide whether a vertex is an end-vertex of DFS or LBFS in linear time on AT-free bigraphs; this improves the LBFS end-vertex complexity on this class of graphs.

With the gradual maturity of component oriented software development method, component-based software evolution technology has become hot research in academia and industry. Although many evolution rules are designed, they rarely consider component type-mismatched problem in evolution rules. This has led to evolution rules that often run error in software evolution execution. Hence, focusing on the mismatch problem of component type in software evolution, this paper addresses various evolution rules with condition constrains to support component type matching. First, we use the bigraph theory to model the software architecture and employ bigraph term language to describe the basic component evolution operations. Second, we join type system into the term language and use the type term language to express the condition constraints on position and connection for component evolution rules. These condition constraints can guarantee the type-matched among components that participate in software evolution. Furthermore, we show that the component type-matched still kept during a number of different evolution rules are used in the whole software evolution reaction system. Finally, two cases study of evolution progress of ATM system and tourism information system are presented. Two cases illustrate the effectiveness of our approach.

The matrix completion problem is the following: Suppose a matrix X is unknown except for an upper bound r on its rank. By sampling various entries of X, is it possible to “complete” the remaining entries and recover X exactly? There are two popular approaches to choosing the entries to be sampled. The first approach is to select these entries at random (either with or without replacement). The second approach is to choose the entries to be sampled in a deterministic fashion; this is the approach studied here. We show that if the entries to be sampled correspond to the edges of a so-called Ramanujan graph (defined below), then the measured matrix is in some sense an “optimal” approximation of the unknown matrix. This naturally raises the question of constructing such Ramanujan graphs. It turns out that there are very few explicit constructions of Ramanujan graphs. In this paper, we review the known methods and analyze their suitability for solving the matrix completion problem. The preceding discussion applies to the completion of square matrices. If one is interested in completing rectangular matrices, then it becomes necessary to choose the sample set to correspond to the edges of a Ramanujan bigraph. Until now, there has not been a single explicit construction of a Ramanujan bigraph. Two such constructions are given here. When specialized to the case of square matrices, our construction generates a new family of Ramanujan graphs.

Ride-sharing (RS) has great values in saving energy and alleviating traffic pressure. Existing studies can be improved for better efficiency. Therefore, we propose a new ride-sharing model, where each driver has a requirement that if the driver shares a ride with a rider, the shared route percentage (i.e., the ratio of the shared route's distance to the driver's total travel distance) exceeds an expectation rate of the driver, e.g., 0.8. We consider two variants of this problem. The first considers multiple drivers and multiple riders and aims to compute driver-rider pairs to maximize the overall shared route percentage (SRP). We model this problem as the maximum weighted bigraph matching problem, where the vertices are drivers and riders, edges are driver-rider pairs, and edge weights are driver-rider's SRP. However, it is rather expensive to compute the SRP values for large numbers of driver-rider pairs on road networks. To address this problem, we propose an efficient method to prune many unnecessary driver-rider pairs and avoid computing the SRP values for every pair. To improve the efficiency, we propose an approximate method with error bound guarantee. The basic idea is that we compute an upper bound and a lower bound for each driver-rider pair in constant time. Then, we estimate an upper bound and a lower bound of the graph matching. Next, we select some driver-rider pairs, compute their real shortest-route distance, and update the lower and upper bounds of the maximum graph matching. We repeat above steps until the ratio of the upper bound to the lower bound is not larger than a given approximate rate. The second considers multiple drivers and a single rider and aims to find the top- $k$ drivers for the rider with the largest SRP. We first prune a large number of drivers that cannot meet the SRP requirements. Then, we propose a best-first algorithm that progressively selects the drivers with high probability to be in the top- $k$ results and prunes the drivers that cannot be in the top- $k$ results. Extensive experiments on real-world datasets demonstrate the superiority of our method.