A Polynomial Time Solution to Minimum Forwarding Set Problem in Wireless Networks under Unit Disk Coverage Model

Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks (WANETs). One promising practical approach for energy-efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multipoint relay (MPR) problem) has received a considerable attention in the research community. Even though the general form of the problem is shown to be NP-complete, the complexity of the problem has not been known under the practical application context of ad hoc networks. In this paper, we present a polynomial time algorithm to solve the MFSP for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy-efficient multicast, broadcast, and topology control protocols for WANETs and sensor networks.     

Microstructure,Phase Composition,and Thermal Stability of Two Zirconium Alloys Subjected to High‐Pressure Torsion at Different Temperatures

The structure, phase composition, and thermal stability of the industrial zirconium alloys, namely, E110 (Zr–1% Nb) and E635 (Zr–1% Nb–0.3% Fe–1.2% Sn), which are subjected to high‐pressure torsion (HPT) at room temperature (RT), 200, and 400 °С have been studied. HPT of Zr‐alloys at RT (10 revolutions) leads to the formation of grain–subgrain nano‐sized structure and to increase the microhardness by 2.1…2.8 times. The increase in the HPT temperature to 200–400 °С leads to the increase in the structural‐element average size. The structural‐element size in the complexly alloyed E635 alloy in all cases is lower compared with the E110 alloy. The hardening of the alloys after HPT at RT and 200 °С is close, and at 400 °С is much less. HPT initiates the α‐Zr → (ω‐Zr + β‐Zr) transformation, which is the main factor for alloys hardening. The α‐Zr → (ω‐Zr + β‐Zr) transformation in the E635 alloy occurs less quickly. The maximum amount (ω‐Zr + β‐Zr) phase in the structure of the alloys is observed after HPT at RT and 200 °C, and the minimum ? at 400 °C. During heating, the alloys undergo the reverse (ω‐Zr + β‐Zr) → α transformation which depends on both the alloy composition and HPT temperature.

     

Beyond Market Baskets: Generalizing Association Rules to Dependence Rules

One of the more well-studied problems in data mining is the search for association rules in market basket data. Association rules are intended to identify patterns of the type: A customer purchasing item A often also purchases item B. Motivated partly by the goal of generalizing beyond market basket data and partly by the goal of ironing out some problems in the definition of association rules, we develop the notion of dependence rules that identify statistical dependence in both the presence and absence of items in itemsets. We propose measuring significance of dependence via the chi-squared test for independence from classical statistics. This leads to a measure that is upward-closed in the itemset lattice, enabling us to reduce the mining problem to the search for a border between dependent and independent itemsets in the lattice. We develop pruning strategies based on the closure property and thereby devise an efficient algorithm for discovering dependence rules. We demonstrate our algorithm's effectiveness by testing it on census data, text data (wherein we seek term dependence), and synthetic data.     

Stabilization and tracking in the nonholonomic integrator via sliding modes

In this paper we use an approach based on sliding mode control to design a feedback which stabilizes the origin for the so-called nonholonomic integrator or Heisenberg system, a particular case of a canonical class of nonlinear driftless control systems of the form

which fail Brockett's necessary condition for the existence of a smooth stabilizing feedback.     

Local ISS of large-scale interconnections and estimates for stability regions

We consider interconnections of locally input-to-state stable (LISS) systems. The class of LISS systems is quite large, in particular it contains input-to-state stable (ISS) and integral input-to-state stable (iISS) systems.Local small-gain conditions both for LISS trajectory and Lyapunov formulations guaranteeing LISS of the composite system are provided in this paper. Notably, estimates for the resulting stability region of the composite system are also given. This in particular provides an advantage over the linearization approach, as will be discussed.     

A generic complete dynamic logic for reasoning about purity and effects

For a number of programming languages, among them Eiffel, C, Java, and Ruby, Hoare-style logics and dynamic logics have been developed. In these logics, pre- and postconditions are typically formulated using potentially effectful programs. In order to ensure that these pre- and postconditions behave like logical formulae (that is, enjoy some kind of referential transparency), a notion of purity is needed. Here, we introduce a generic framework for reasoning about purity and effects. Effects are modelled abstractly and axiomatically, using Moggi’s idea of encapsulation of effects as monads. We introduce a dynamic logic (from which, as usual, a Hoare logic can be derived) whose logical formulae are pure programs in a strong sense. We formulate a set of proof rules for this logic, and prove it to be complete with respect to a categorical semantics. Using dynamic logic, we then develop a relaxed notion of purity which allows for observationally neutral effects such writing on newly allocated memory.     

Business process model abstraction: a definition, catalog, and survey

The discipline of business process management aims at capturing, understanding, and improving work in organizations by using process models as central artifacts. Since business-oriented tasks require different information from such models to be highlighted, a range of abstraction techniques has been developed over the past years to manipulate overly detailed models. At this point, a clear understanding of what distinguishes these techniques and how they address real world use cases has not yet been established. In this paper we systematically develop, classify, and consolidate the use cases for business process model abstraction and present a case study to illustrate the value of this technique. The catalog of use cases that we present is based on a thorough evaluation of the state of the art, as well as on our cooperation with end users in the health insurance sector. It has been subsequently validated by experts from the consultancy and tool vendor domains. Based on our findings, we evaluate how the existing business process model abstraction approaches support the discovered use cases and reveal which areas are not adequately covered, as such providing an agenda for further research in this area.     

Global uniform input-to-state stabilization of large-scale interconnections of MIMO generalized triangular form switched systems

We solve the problem of global uniform input-to-state stabilization with respect to external disturbance signals for a class of large-scale interconnected nonlinear switched systems. The overall system is composed of switched subsystems each of which has the nonlinear MIMO generalized triangular form, which (in contrast to strict-feedback form) has non-invertible input–output maps. The switching signal is an arbitrary unknown piecewise constant function and the feedback constructed does not depend on the switching signal.     

From fine-grained to abstract process models: A semantic approach

Organizations actively managing their business processes face a rapid growth of the number of process models that they maintain. Business process model abstraction has proven to be an effective means to generate readable, high-level views on business process models by showing coarse-grained activities and leaving out irrelevant details. In this way, abstraction facilitates a more efficient management of process models, as a single model can provide for many relevant views. Yet, it is an open question how to perform abstraction in the same skillful way as experienced modelers combine activities into more abstract tasks. This paper presents an approach that uses semantic information of a process model to decide on which activities belong together, which extends beyond existing approaches that merely exploit model structural characteristics. The contribution of this paper is twofold: we propose a novel activity aggregation method and suggest how to discover the activity aggregation habits of human modelers. In an experimental validation, we use an industrial process model repository to compare the developed activity aggregation method with actual modeling decisions, and observe a strong correlation between the two. The presented work is expected to contribute to the development of modeling support for the effective process model abstraction.