Revisiting bounded context block‐sorting transformations

The Burrows–Wheeler Transform (BWT ) produces a permutation of a string X, denoted X^?, by sorting the n cyclic rotations of X into full lexicographical order and taking the last column of the resulting n×n matrix to be X^?. The transformation is reversible in time. In this paper, we consider an alteration to the process, called k‐BWT , where rotations are only sorted to a depth k. We propose new approaches to the forward and reverse transform, and show that the methods are efficient in practice. More than a decade ago, two algorithms were independently discovered for reversing k‐BWT , both of which run in time. Two recent algorithms have lowered the bounds for the reverse transformation to and, respectively. We examine the practical performance for these reversal algorithms. We find that the original approach is most efficient in practice, and investigates new approaches, aimed at further speeding reversal, which store precomputed context boundaries in the compressed file. By explicitly encoding the context boundaries, we present an reversal technique that is both efficient and effective. Finally, our study elucidates an inherently cache‐friendly – and hitherto unobserved – behavior in the reverse k‐BWT , which could lead to new applications of the k‐BWT transform. In contrast to previous empirical studies, we show that the partial transform can be reversed significantly faster than the full transform, without significantly affecting compression effectiveness. Copyright © 2011 John Wiley & Sons, Ltd.     

Determinization and minimization of finite acyclic automata by incremental techniques

The determinization of a nondeterministic finite automaton (FA) is the process of generating a deterministic FA (DFA) equivalent to (sharing the same regular language of) . The minimization of is the process of generating the minimal DFA equivalent to . Classical algorithms for determinization and minimization are available in the literature for several decades. However, they operate monolithically, assuming that the FA to be either determinized or minimized is given once and for all. By contrast, we consider determinization and minimization in a dynamic context, where augments over time: after each augmentation, determinization and minimization of into is required. Using classical monolithic algorithms to solve this problem is bound to poor performance. An algorithm for incremental determinization and minimization of acyclic finite automata, called IDMA, is proposed. Despite being conceived within the narrow domain of model‐based diagnosis and monitoring of active systems, the algorithm is general‐purpose in nature. Experimental evidence indicates that IDMA is far more efficient than classical algorithms in solving incremental determinization and minimization problems. Copyright © 2015 John Wiley & Sons, Ltd.     

Another view on q‐rung orthopair fuzzy sets

In this paper, two new approaches have been presented to view q‐rung orthopair fuzzy sets. In the first approach, these can viewed as L‐fuzzy sets, whereas the second approach is based on the notion of orbits. Uncertainty index is the quantity , which remains constant for all points in an orbit. Certain operators can be defined in q‐ROF sets, which affect when applied to some q‐ROF sets. Operators , , and have been defined. It is studied that how these operators affect when applied to some q‐ROF set A.     

Investigation of higher order modes excitation through F‐shaped slot in rectangular dielectric resonator antenna for wideband circular polarization with broadside radiation characteristics

In this article, a wideband circularly polarized rectangular dielectric resonator antenna (RDRA) with broadside radiation characteristics has been proposed. By using modified ground plane having an F‐shaped slot, the proposed structure able to generates three sets of modes i.e., fundamental as well as higher order modes. To obtained circular polarization, an orthogonal mode (TE₁₁₃) in the RDRA has been generated by using the F‐shaped slot on the modified ground plane. The resonance frequency of fundamental mode (TE₁₁₁) in the rectangular dielectric resonator (DR) has been calculated by using dielectric waveguide model method. The same has been confirmed through E‐field distribution in RDRA. Here, wide axial ratio (AR) bandwidth of the proposed antenna is due to the generation of and modes. It is observed that input impedance bandwidth has been broadening with a pair of excited modes ( and modes) in the proposed antenna structure. All these modes have been excited and merged to form a wide input impedance bandwidth and wide AR bandwidth of the designed antenna. The proposed antenna shows measured input reflection coefficient (S₁₁ < ?10 dB) of 50.55% and measured AR bandwidth (AR < 3 dB) of 14.28%. The designed antenna shows left‐handed circular polarization in broadside direction and offering an average gain and radiation efficiency of 4.29 dBic and 92.22% respectively.     

Dynamic output‐feedback control for continuous‐time singular Markovian jump systems

This paper considers a dynamic output‐feedback control for continuous‐time singular Markovian jump systems, whereas the existing research studies in literature focused on state‐feedback or static output‐feedback control. While they have only provided the sufficient conditions, this paper successfully obtains the necessary and sufficient condition for the existence of the dynamic output‐feedback control. Furthermore, this condition is expressed with linear matrix inequalities by the so‐called replacement technique. Two numerical examples show the validity of the resulting control.     

Full complexity analysis of the diameter‐constrained reliability

Let be a simple graph with nodes and links, a subset of “terminals,” a vector , and a positive integer d, called “diameter.” We assume that nodes are perfect but links fail stochastically and independently, with probabilities . The “diameter‐constrained reliability” (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of d links, or less. This number is denoted by . The general DCR computation belongs to the class of ‐hard problems, since it subsumes the problem of computing the probability that a random graph is connected. The contributions of this paper are twofold. First, a full analysis of the computational complexity of DCR subproblems is presented in terms of the number of terminal nodes and the diameter d. Second, we extend the class of graphs that accept efficient DCR computation. In this class, we include graphs with bounded co‐rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant to robust network design.     

Thin‐slot formalism for the split‐field FDTD analysis of periodic structure

An expression of the thin‐slot formalism is presented to alleviate the gridding of the split‐field finite‐difference time‐domain (FDTD) solution for periodic structure. The varying auxiliary‐field ( , ) and split‐field ( , ) distributions near the slots are analytically derived from the varying field ( , ). The update equations for the split‐field FDTD are obtained by incorporating those varying field distributions into the split‐field equations in integral form. A frequency selective surface (FSS) structure is applied to verify the proposed method. The results indicate that the computational efficiency is improved.     

Design and analysis of wideband U‐slot patch antenna with U‐shaped parasitic elements

A single layer single probe‐fed wideband microstrip antenna is presented and investigated. By cutting a U‐slot in the rectangular patch, and by incorporating two identical U‐shaped parasitic patches around both the radiating edges and the nonradiating edges of the rectangular patch, three resonant frequencies are excited to form the wideband performance. Details of the antenna design is presented. The measured and simulated results are in good agreement, the measured impedance bandwidth is GHz ( GHz), or centered at GHz, which covers WLAN GHz ( GHz), WLAN GHz ( GHz), and WIMAX GHz ( GHz) bands. The measured peak gains at the three resonant frequencies are dB, dB, and dB, respectively. An equivalent circuit model which is based on the transmission line theory, the asymmetric coupled microstrip lines theory, and the π‐network theory is established. This equivalent circuit model is used to give an insight into the wideband mechanism of the proposed antenna, and is also used to explain why the three resonant frequencies shift at the variations of different parameters from a physical point of view. The error analysis is given to demonstrate the validity of the equivalent circuit model.     

Distributed filtering and synchronization of diffusively state‐coupled heterogeneous systems

This paper studies distributed filtering‐based ssynchronization of diffusively state‐coupled heterogeneous systems. For given heterogeneous subsystems and a network topology, sufficient conditions for the filtering‐based synchronization are developed with a guaranteed performance. The estimation and synchronization error dynamics are obtained in a decoupled form, and it is shown that the filter and the controller can be designed separately by LMIs. The feasibility of the proposed design method using LMIs is discussed, and the main results are validated through examples with various setup. Copyright © 2016 John Wiley & Sons, Ltd.     

Prize‐collecting set multicovering with submodular pricing

We consider a ground set E and a submodular function acting on it. We first propose a “set multicovering” problem in which the value (price) of any is . We show that the linear program (LP) of this problem can be directly solved by applying a submodular function minimization (SFM) algorithm on the dual LP. However, the main results of this study concern prize‐collecting multicovering with submodular pricing, that is, a more general and more difficult “multicovering” problem in which elements can be left uncovered by paying a penalty. We formulate it as a large‐scale LP (with variables representing all subsets of E) that could be tackled by column generation (CG; for a CG algorithm for “set‐covering” problems with submodular pricing). However, we do not solve this large‐scale LP by CG, but we solve it in polynomial time by exploiting its integrality properties. More exactly, after appropriate restructuring, the dual LP can be transformed into an LP that has been thoroughly studied (as a primal) in the SFM theory. Solving this LP reduces to optimizing a strong map of submodular functions. For this, we use the Fleischer–Iwata framework that optimizes all these functions within the same asymptotic running time as solving a single SFM, that is, in , where and γ is the complexity of one submodular evaluation. Besides solving the problem, the proposed approach can be useful to (a) simultaneously find the best solution of up to functions under strong map relations in time, (b) perform sensitivity analysis in very short time (even at no extra cost), and (c) reveal combinatorial insight into the primal–dual optimal solutions. We present several potential applications throughout the paper, from production planning to combinatorial auctions.     

A new dual‐mode wideband circularly polarized rectangular dielectric resonator antenna coupled with stubs and asymmetric ground plane for WiMAX applications

In this article, a new radiating stub microstrip feed has been investigated with asymmetrical ground plane for generation of circular polarization (CP) in a dielectric resonator antenna (DRA). Here, asymmetrical ground plane and 3 radiating stubs with microstrip feed line are used for generation of 2 different modes namely TE_11δ and TE_12δ in rectangular DRA. By using mode matching concepts, these modes are responsible for enhancing the impedance bandwidth (TE_12δ ie, and ) and axial ratio (AR) bandwidth (TE_11δ ie, and ) in proposed antenna. Designed antenna offers measured input impedance bandwidth (|S₁₁| < ?10 dB) and AR bandwidth (AR < 3‐dB) of 44.78%, ranging from 4.6 to 6.9 GHz and 23.32%, ranging from 4.6 to 6.9 GHz, respectively. It has been observed that proposed antenna shows left‐handed CP fields in boresight direction with average gain of 3.15 dBic and radiation efficiency of 90.54%. Designed antenna is suitable for Wi‐MAX (3.3‐3.7 GHz) applications.     

Spline Based Pseudo‐Inversion of Sampled Data Non‐Minimum Phase Systems for an Almost Exact Output Tracking

This paper considers the problem of achieving a very accurate tracking of a pre‐specified desired output trajectory , for linear, multiple input multiple output, non‐minimum phase and/or non hyperbolic, sampled data, and closed loop control systems. The proposed approach is situated in the general framework of model stable inversion and introduces significant novelties with the purpose of reducing some theoretical and numerical limitations inherent in the methods usually proposed. In particular, the new method does not require either a preactuation or null initial conditions of the system. The desired and the corresponding sought input are partitioned in a transient component ( and u_t(k), respectively) and steady‐state ( and u_s(k), respectively). The desired transient component is freely assigned without requiring it to be null over an initial time interval. This drastically reduces the total settling time. The structure of u_t(k) is a priori assumed to be given by a sampled smoothing spline function. The spline coefficients are determined as the least‐squares solution of the over‐determined system of linear equations obtained imposing that the sampled spline function assumed as reference input yield the desired output over a properly defined transient interval. The steady‐state input u_s(k) is directly analytically computed exploiting the steady‐state output response expressions for inputs belonging to the same set of .     

Low Frequency Sensitivity Function Constraints for Nonlinear ‐stable Networked Control

The paper derives a robust networked controller design method for systems with saturation where the delay is large and uncertain, as in one‐directional data flow‐control. A classical linear H_∞ criterion is first formulated in terms of the sensitivity and complementary sensitivity functions. A new asymptotic constraint is then derived, which specifies the minimum amount of low frequency gain that is needed in the sensitivity function to conclude on non‐linear closed loop ‐stability using the Popov criterion. This result guides the selection of the design criterion, thereby adjusting the linear controller design for better handling of delay and saturation. The controller design method then uses gridding to pre‐compute a subset of the stability region. Based on the pre‐computed region, a robust ‐stable controller can be selected. Alternatively, an adaptive controller could recompute ‐stable controllers on‐line using the pre‐computed region. Simulations show that the controller meets the specified stability and performance requirements.     

Decentralized weighted control for a class of large‐scale systems with multi‐modes

In this paper, the control synthesis problem for a class of large‐scale systems with multi‐modes that are called large‐scale switched systems is addressed. By introducing the concept of decentralized switching signal and the relevant decentralized average dwell time, the asymptotic stability and weighted ?₂ gain performance are investigated. It should be noted that the decentralized switching covers general switching cases for large‐scale switched systems, namely, it admits both time‐dependent switching signal and arbitrary switching signal blended in the decentralized switching. Then, on the basis of the analysis results, the decentralized weighted control scheme including state feedback controller gains and switching signals is studied. Several design algorithms are proposed to meet different controller design problems. Finally, numerical examples are provided to illustrate theoretical findings within this paper. Copyright © 2013 John Wiley & Sons, Ltd.     

Polynomial time approximation algorithms for proportionate open‐shop scheduling

This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if , where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, , we develop a polynomial time approximation algorithm with a worst‐case performance ratio of that improves the bound existing for general open‐shops. Next, in the case of , we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where .     

Graphical tuning method of FOPID controllers for fractional order uncertain system achieving robust ‐stability

This paper focuses on the graphical tuning method of fractional order proportional integral derivative (FOPID) controllers for fractional order uncertain system achieving robust ‐stability. Firstly, general result is presented to check the robust ‐stability of the linear fractional order interval polynomial. Then some alternative algorithms and results are proposed to reduce the computational effort of the general result. Secondly, a general graphical tuning method together with some computational efficient algorithms are proposed to determine the complete set of FOPID controllers that provides ‐stability for interval fractional order plant. These methods will combine the results for fractional order parametric robust control with the method of FOPID ‐stabilization for a fixed plant. At last, two important extensions will be given to the proposed graphical tuning methods: determine the ‐stabilizing region for fractional order systems with two kinds of more general and complex uncertainty structures: multi‐linear interval uncertainty and mixed‐type uncertainties. Numerical examples are followed to illustrate the effectiveness of the method. Copyright © 2015 John Wiley & Sons, Ltd.     

Greedy Geometric Algorithms for Collection of Balls,with Applications to Geometric Approximation and Molecular Coarse‐Graining

Choosing balls that best approximate a 3D object is a non‐trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object defined by a union of n balls with balls defining a region . This solution is further used to construct an outer approximation enclosing the initial shape, and an interpolated approximation sandwiched between the inner and outer approximations. The inner approximation problem is reduced to a geometric generalization of weighted max k‐cover, solved with the greedy strategy which achieves the classical lower bound. The outer approximation is reduced to exploiting the partition of the boundary of by the Apollonius Voronoi diagram of the balls defining the inner approximation. Implementation‐wise, we present robust software incorporating the calculation of the exact Delaunay triangulation of points with degree two algebraic coordinates, of the exact medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. Application‐wise, we exhibit accurate coarse‐grain molecular models using a number of balls 20 times smaller than the number of atoms, a key requirement to simulate crowded cellular environments.     

r‐consensus control for higher‐order multi‐agent systems with digraph

This paper studies a consensus problem for lth (l ≥ 2) order multi‐agent systems with digraph, namely, for a fixed r (0 ≤ r ≤ l ? 1), the rth derivative of the states x_i of agents are convergent to a constant value and, for every k (0 ≤ k ≤ l ? 1), are convergent to zeros. A new concept of r‐consensus is introduced and new consensus protocols are proposed for solving such an r‐consensus problem. A sufficient and necessary condition for r‐consensus is obtained. As special cases, criteria for third‐order systems are given, in which the exact relationship between feedback gains is established. Finally, an illustrative example is given to demonstrate the effectiveness of these protocols.     

Quasi‐Time‐Dependent Controller for Discrete‐Time Switched Linear Systems With Mode‐Dependent Average Dwell‐Time

This paper is concerned with the stability and stabilization problem of a class of discrete‐time switched systems with mode‐dependent average dwell time (MDADT). A novel Lyapunov function, which is both mode‐dependent (MD) and quasi‐time‐dependent (QTD), is established. The new established Lyapunov function is allowed to increase at some certain time instants. A QTD controller is designed such that the system is globally uniformly asymptotically stable (GUAS) and has a guaranteed performance index. The new QTD robust controller designed in this paper is less conservative than the mode independent one which is frequently considered in literatures. Finally, a numerical example and a practical example are provided to illustrate the effectiveness of the developed results.      

On computing the 2‐diameter ‐constrained K ‐reliability of networks

This article considers a communication network modeled by a graph and a distinguished set of terminal nodes . We assume that the nodes never fail, but the edges fail randomly and independently with known probabilities. The classical K ‐reliability problem computes the probability that the subnetwork is composed only by the surviving edges in such a way that all terminals communicate with each other. The d ‐diameter ‐constrained K ‐reliability generalization also imposes the constraint that each pair of terminals must be the extremes of a surviving path of approximately d length. It allows modeling communication network situations in which limits exist on the acceptable delay times or on the amount of hops that packets can undergo. Both problems have been shown to be NP ‐hard, yet the complexity of certain subproblems remains undetermined. In particular, when , it was an open question whether the instances with were solvable in polynomial time. In this paper, we prove that when and is a fixed parameter (i.e. not an input) the problem turns out to be polynomial in the number of nodes of the network (in fact linear). We also introduce an algorithm to compute these cases in such time and also provide two numerical examples.