(Tissue) P systems working in the k-restricted minimally or maximally parallel transition mode

We investigate variants of the maximally and the minimally parallel transition mode, i.e., we allow only a bounded number of rules to be taken from every set of the partitioning of the whole set of rules. The 1-restricted minimally parallel transition mode especially fits to describe the way transitions take place in spiking neural P systems without delays, i.e., in every neuron where a rule is applicable exactly one rule has to be applied. Moreover, purely catalytic P systems working in the maximally parallel transition mode can be described as P systems using the corresponding rules without catalysts, i.e., noncooperative rules, when working in the 1-restricted minimally parallel transition mode. In contrast to these results for computationally complete models of P systems, with the k-restricted maximally parallel transition mode noncooperative rules only allow for the generation of semi-linear sets.     

From SOS Specifications to Structured Coalgebras: How to Make Bisimulation a Congruence

In this paper we address the issue of providing a structured coalgebra presentation of transition systems with algebraic structure on states determined by an equational specification Γ. More precisely, we aim at representing such systems as coalgebras for an endofunctor on the category of Γ-algebras. The systems we consider are specified by using a quite general format of SOS rules, the algebraic format, which in general does not guarantee that bisimilarity is a congruence.We first show that the structured coalgebra representation works only for systems where transitions out of complex states can be derived from transitions out of corresponding component states. This decomposition property of transitions indeed ensures that bisimilarity is a congruence. For a system not satisfying this requirement, next we propose a closure construction which adds context transitions, i.e., transitions that spontaneously embed a state into a bigger context or vice-versa. The notion of bisimulation for the enriched system coincides with the notion of dynamic bisimilarity for the original one, that is, with the coarsest bisimulation which is a congruence. This is sufficient to ensure that the structured coalgebra representation works for the systems obtained as result of the closure construction.     

High-Impact Bug Report Identification with Imbalanced Learning Strategies

In practice, some bugs have more impact than others and thus deserve more immediate attention. Due to tight schedule and limited human resources, developers may not have enough time to inspect all bugs. Thus, they often concentrate on bugs that are highly impactful. In the literature, high-impact bugs are used to refer to the bugs which appear at unexpected time or locations and bring more unexpected effects (i.e., surprise bugs), or break pre-existing functionalities and destroy the user experience (i.e., breakage bugs). Unfortunately, identifying high-impact bugs from thousands of bug reports in a bug tracking system is not an easy feat. Thus, an automated technique that can identify high-impact bug reports can help developers to be aware of them early, rectify them quickly, and minimize the damages they cause. Considering that only a small proportion of bugs are high-impact bugs, the identification of high-impact bug reports is a difficult task. In this paper, we propose an approach to identify high-impact bug reports by leveraging imbalanced learning strategies. We investigate the effectiveness of various variants, each of which combines one particular imbalanced learning strategy and one particular classification algorithm. In particular, we choose four widely used strategies for dealing with imbalanced data and four state-of-the-art text classification algorithms to conduct experiments on four datasets from four different open source projects. We mainly perform an analytical study on two types of high-impact bugs, i.e., surprise bugs and breakage bugs. The results show that different variants have different performances, and the best performing variants SMOTE (synthetic minority over-sampling technique) + KNN (K-nearest neighbours) for surprise bug identification and RUS (random under-sampling) + NB (naive Bayes) for breakage bug identification outperform the F1-scores of the two state-of-the-art approaches by Thung et al. and Garcia and Shihab.     

A Kleene theorem and model checking algorithms for existentially bounded communicating automata

The behavior of a network of communicating automata is called existentially bounded if communication events can be scheduled in such a way that the number of messages in transit is always bounded by a value that depends only on the machine, not the run itself. We show a Kleene theorem for existentially bounded communicating automata, namely the equivalence between communicating automata, globally cooperative compositional message sequence graphs, and monadic second order logic. Our characterization extends results for universally bounded models, where for each and every possible scheduling of communication events, the number of messages in transit is uniformly bounded. As a consequence, we give solutions in spirit of Madhusudan (2001) for various model checking problems on networks of communicating automata that satisfy our optimistic restriction.     

Compositional encoding for bounded model checking

Verification techniques like SAT-based bounded model checking have been successfully applied to a variety of system models. Applying bounded model checking to compositional process algebras is, however, a highly non-trivial task. One challenge is that the number of system states for process algebra models is not statically known, whereas exploring the full state space is computationally expensive. This paper presents a compositional encoding of hierarchical processes as SAT problems and then applies state-of-the-art SAT solvers for bounded model checking. The encoding avoids exploring the full state space for complex systems so as to deal with state space explosion. We developed an automated analyzer which combines complementing model checking techniques (i.e., bounded model checking and explicit onthe-fly model checking) to validate system models against event-based temporal properties. The experiment results show the analyzer handles large systems.     

Decentralized Guidance Control of UAVs with Explicit Optimization of Communication

We design a decentralized guidance control method for autonomous unmanned aerial vehicles (UAVs) tracking multiple targets. We formulate this guidance control problem as a decentralized partially observable Markov decision process (Dec-POMDP). As in the case of partially observable Markov decision process (POMDP), it is intractable to solve a Dec-POMDP exactly. So, we extend a POMDP approximation method called nominal belief-state optimization (NBO) to solve our control problem posed as a Dec-POMDP. We incorporate the cost of communication into the objective function of the Dec-POMDP, i.e., we explicitly optimize the communication among the UAVs at the network level along with the kinematic control commands for the UAVs. We measure the performance of our method with the following metrics: 1) average target-location error, and 2) average communication cost. The goal to maximize the performance with respect to each of the above metrics conflict with each other, and we show through empirical study how to trade off between these performance metrics using a scalar parameter. The NBO method induces coordination among the UAVs even though the system is decentralized. To demonstrate the effectiveness of this coordination, we compare our Dec-POMDP approach with a greedy approach (a noncooperative approach), where the UAVs do not communicate with each other and each UAV optimizes only its local kinematic controls. Furthermore, we compare the performance of our approach of optimizing the communication between the UAVs with a fixed communication scheme—where only the UAV kinematic controls are optimized with an underlying fixed (non-optimized) communication scheme.     

Evaluation and comparison of various indexing schemes in single-channel broadcast communication environment

Wireless Data Broadcasting is a newly developed data dissemination method for spreading public information to a tremendous number of mobile subscribers. Access Latency and Tuning Time are two main criteria to evaluate the performance of such system. With the help of indexing technology, clients can reduce tuning time significantly by searching indices first and turning to doze mode during waiting period. Different indexing schemes perform differently, so we can hardly compare the efficiency of different indexing schemes. In this paper, we redesigned several most popular indexing schemes for data broadcasting systems, i.e., distributed index, exponential index, hash table, and Huffman tree index. We created a unified communication model and constructed a novel evaluation strategy by using the probability theory to formulate the performance of each scheme theoretically and then conducted simulations to compare their performance by numerical experiments. This is the first work to provide scalable communication environment and accurate evaluation strategies. Our communication model can easily be modified to meet specific requirements. Our comparison model can be used by the service providers to evaluate other indexing schemes to choose the best one for their systems.     

Can I find a partner? Undecidability of partner existence for open nets

We study open nets as Petri net models of web services, with a link to the practically relevant language WS-BPEL. For those nets, we investigate the problem of operability which we consider as fundamental as the successful notion of soundness for workflow nets, i.e., Petri net models of business processes and workflows. While we could give algorithmic solutions to the operability problem for subclasses of open nets in earlier work, this article shows that the problem is in general undecidable.     

A parametric analysis of the state-explosion problem in model checking

In model checking, the state-explosion problem occurs when one checks a nonflat system, i.e., a system implicitly described as a synchronized product of elementary subsystems. In this paper, we investigate the complexity of a wide variety of model-checking problems for nonflat systems under the light of parameterized complexity, taking the number of synchronized components as a parameter. We provide precise complexity measures (in the parameterized sense) for most of the problems we investigate, and evidence that the results are robust.     

Spaceability for sets of bandlimited input functions and stable linear time-invariant systems with finite time blowup behavior

The approximation of linear time-invariant systems by sampling series is studied for bandlimited input functions in the Paley–Wiener space PW _π ¹ , i.e., bandlimited signals with absolutely integrable Fourier transform. It has been known that there exist functions and systems such that the approximation process diverges. In this paper we identify a signal set and a system set with divergence, i.e., a finite time blowup of the Shannon sampling expression. We analyze the structure of these sets and prove that they are jointly spaceable, i.e., each of them contains an infinite-dimensional closed subspace such that for any function and system pair from these subspaces, except for the zero elements, we have divergence.     

Pure Nash equilibria in player-specific and weighted congestion games

Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there exist pure equilibria for both of these variants in the case of singleton congestion games, i.e., if the players’ strategy spaces contain only sets of cardinality one. In this paper, we investigate how far such a property on the players’ strategy spaces guaranteeing the existence of pure equilibria can be extended. We show that both weighted and player-specific congestion games admit pure equilibria in the case of matroid congestion games, i.e., if the strategy space of each player consists of the bases of a matroid on the set of resources. We also show that the matroid property is the maximal property that guarantees pure equilibria without taking into account how the strategy spaces of different players are interweaved.     

How to Use Spanning Trees to Navigate in Graphs

In this paper, we investigate three strategies of how to use a spanning tree T of a graph G to navigate in G, i.e., to move from a current vertex x towards a destination vertex y via a path that is close to optimal. In each strategy, each vertex v has full knowledge of its neighborhood N _G [v] in G (or, k-neighborhood D _k (v,G), where k is a small integer) and uses a small piece of global information from spanning tree T (e.g., distance or ancestry information in T), available locally at v, to navigate in G. We investigate advantages and limitations of these strategies on particular families of graphs such as graphs with locally connected spanning trees, graphs with bounded length of largest induced cycle, graphs with bounded tree-length, graphs with bounded hyperbolicity. For most of these families of graphs, the ancestry information from a Breadth-First-Search-tree guarantees short enough routing paths. In many cases, the obtained results are optimal up to a constant factor.     

MIND: An approach to optimize communication time via middleware tuning

Minimizing the communication time due to the transfer over a network of the intermediary results produced during the execution of a distributed query is a fundamental problem in distributed database management systems. We take a new look at this problem by investigating the relationship between the communication time and a remote data access middleware. We focus on two middleware parameters that are manually tuned by database administrators or programmers: the fetch size (i.e., the number of tuples that are communicated at once) and the message size (i.e., the size of the buffer at the middleware level). We present an experimental study which shows that these parameters have a crucial impact on the communication time. Then, we propose the MIND framework, which tunes the aforementioned middleware parameters, while adapting to different queries (that may vary in terms of selectivity) and networks (that may vary in terms of bandwidth). The main technical contributions of MIND are (i) a communication time estimation function that takes into account the middleware parameters, the size of the query result and the network environment, and (ii) an iterative optimization algorithm to find the fetch size and the message size that allow a good trade-off between low resource consumption and low communication time. We conclude with an experimental study that emphasizes the effectiveness of the MIND framework.     

Virtual reality as a communication process

In this work, we consider immersive Virtual Reality (VR) as a communication process between humans, mediated by computer systems, which uses interaction, visualization, and other sensory stimuli to convey information. From this viewpoint, it is relevant to understand how VR can solve a given communication problem, what is therefore the expressive power of VR system, i.e., its ability in establishing the communication, what are the guidelines to design an effective system, and what are the more relevant models of VR applications. Firstly, we try to clarify the notion of reality in Virtual Reality systems and conclude that reality is not an intrinsic characteristic of VR, rather the result of a conventional way of coding information. The purpose of coding is to lead the observer to the conclusion that the VR set is what is called in italian as verisimile (from Latin veri similis), i.e., ??similar-to-the-real-thing??. So the creation of an effective VR application is an artifice or an illusion. But in order to avoid an over-reliance on the creativity of the VR designer, we intend to identify a solid ground on which different kinds of VR solutions can be considered in terms of their ability to solve the desired communication objective. To this aim, we will rely on methods derived from rhetoric to semiotics.     

High fidelity and flexible quantum state transfer in the atom-coupled cavity hybrid system

We investigate a system composed of N coupled cavities (linear array) and two-level atoms interacting one at a time. Adjusting appropriately the atom-field detuning, and making the hopping rate of photons between neighboring cavities, A, greater than the atom-field coupling g (i.e. A ? N ^3/2 g), we can eliminate the interaction of the atom with the non-resonant normal modes reducing the dynamics to the interaction of the atom with only a single-mode. As an application of this interaction, we propose a two-step protocol for quantum communication of an arbitrary atomic quantum state between distant coupled cavities. In the ideal case, the coupled cavities system acts as a perfect quantum bus and we obtain a flexible and perfect quantum communication for any N. Considering the influence of dissipation, an interesting parity effect emerges and we still obtain a high fidelity quantum state transfer for an appreciable number of cavities with current experimental parameters. We also studied important sources of imperfections during the procedure.     

Re-Chord: A Self-stabilizing Chord Overlay Network

The Chord peer-to-peer system is considered, together with CAN, Tapestry and Pastry, as one of the pioneering works on peer-to-peer distributed hash tables (DHT) that inspired a large volume of papers and projects on DHTs as well as peer-to-peer systems in general. Chord, in particular, has been studied thoroughly, and many variants of Chord have been presented that optimize various criteria. Also, several implementations of Chord are available on various platforms. Though Chord is known to be very efficient and scalable and it can handle churn quite well, no protocol is known yet that guarantees that Chord is self-stabilizing, i.e., the Chord network can be recovered from any initial state in which the network is still weakly connected. This is not too surprising since it is known that the Chord network is not locally checkable for its current topology. We present a slight extension of the Chord network, called Re-Chord (reactive Chord), that turns out to be locally checkable, and we present a self-stabilizing distributed protocol for it that can recover the Re-Chord network from any initial state, in which the n peers are weakly connected. in O(nlogn) communication rounds. We also show that our protocol allows a new peer to join or an old peer to leave an already stable Re-Chord network so that within O((logn)²) communication rounds the Re-Chord network is stable again.     

Bounded self-stabilizing Petri nets

We investigate the property of self-stabilization in bounded Petri nets. We give characterizations for both self-stabilizing bounded ordinary Petri nets (i.e., Petri nets without multiple arcs) and self-stabilizing bounded general Petri nets (i.e., Petri nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri nets and PSPACE-complete for bounded general Petri nets.Louis Rosier passed away on May 6, 1991, while this paper was under review     

Infinite-state high-level MSCs: Model-checking and realizability

Message sequence charts (MSC) and High-level MSC (HMSC) is a visual notation for asynchronously communicating processes and a standard of the ITU. They usually represent incomplete specifications of required or forbidden properties of communication protocols. We consider in this paper two basic problems concerning the automated validation of HMSC specifications, namely model-checking and synthesis. We identify natural syntactic restrictions of HMSCs for which we can solve the above questions. We show first that model-checking for globally cooperative (and locally cooperative) HMSCs is decidable within the same complexity as for the restricted class of bounded HMSCs. Furthermore, model-checking local-choice HMSCs turns out to be as efficient as for finite-state (sequential) systems. The study of locally cooperative and local-choice HMSCs is motivated by the synthesis question, i.e., the question of implementing HMSCs through communicating finite-state machines (CFM) with additional message data. We show that locally cooperative and local-choice HMSCs are always implementable. Furthermore, the implementation of a local-choice HMSC is deadlock-free and of linear size.     

Investigating recognition-based performance in an open content community: A social capital perspective

As the open source movement grows, it becomes important to understand the dynamics that affect the motivation of participants who contribute their time freely to such projects. One important motivation that has been identified is the desire for formal recognition in the open source community. We investigated the impact of social capital in participants’ social networks on their recognition-based performance; i.e., the formal status they are accorded in the community. We used a sample of 465 active participants in the Wikipedia open content encyclopedia community to investigate the effects of two types of social capital and found that network closure, measured by direct and indirect ties, had a significant positive effect on increasing participants’ recognition-based performance. Structural holes had mixed effects on participants’ status, but were generally a source of social capital.