On a new class of fuzzy implications: h-Implications and generalizations

A new class of fuzzy implications called the h-implications is introduced. They are implications generated from an additive generator of a representable uninorm in a similar way of Yager’s f- and g-implications which are generated from additive generators of continuous Archimedean t-norms and t-conorms. Basic properties of these implications are studied in detail. Modifications and generalizations of the initial definition are presented and their properties studied and compared between them. One of the modifications, called (h, e)-implications, is another example of a fuzzy implication satisfying the exchange principle but not the law of importation for any t-norm, in fact for any function F : [0, 1]² → [0, 1].     

On ∗-λ-semirings

A ∗-λ-semiring is an ordered semiring S equipped with a star operation such that for any a, b ∈ S, a^∗b is the least fixed point of the linear mapping x ? ax + b over S. The notion of ∗-λ-semirings is a generalization of several important concepts such as continuous semirings, (weak) inductive ∗-semirings and the Kleene algebras of Conway and Kozen. We investigate several basic properties of ∗-λ-semirings and obtain results on ∗-λ-semirings in relation to preorders, duality and formal power series. Some of these results can be seen as generalizations of relevant results on inductive ∗-semirings.     

Efficient continuous skyline computation

In a number of emerging streaming applications, the data values that are produced have an associated time interval for which they are valid. A useful computation over such streaming data is to produce a continuous and valid skyline summary. Previous work on skyline algorithms have only focused on evaluating skylines over static data sets, and there are no known algorithms for skyline computation in the continuous setting. In this paper, we introduce the continuous time-interval skyline operator, which continuously computes the current skyline over a data stream. We present a new algorithm called LookOut for evaluating such queries efficiently, and empirically demonstrate the scalability of this algorithm. In addition, we also examine the effect of the underlying spatial index structure when evaluating skylines. Whereas previous work on skyline computations have only considered using the R^∗-tree index structure, we show that for skyline computations using an underlying quadtree has significant performance benefits over an R^∗-tree index.     

The m-pancycle-connectivity of a WK-Recursive network

In this paper, we study the m-pancycle-connectivity of a WK-Recursive network. We show that a WK-Recursive network with amplitude W and level L is strictly (5 × 2^L−1 − 2)-pancycle-connected for W ? 3. That is, each pair of vertices in a WK-recursive network with amplitude greater than or equal to 3 resides in a common cycle of every length ranging from 5 × 2^L−1 − 2 to N, where N is the size of the interconnection network; and the value 5 × 2^L−1 − 2 reaches the lower bound of the problem.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

A fast pattern matching algorithm with multi-byte search unit for high-speed network security

A signature-based intrusion detection system identifies intrusions by comparing the data traffic with known signature patterns. In this process, matching of packet strings against signature patterns is the most time-consuming step and dominates the overall system performance. Many signature-based network intrusion detection systems (NIDS), e.g., the Snort, employ one or multiple pattern matching algorithms to detect multiple attack types. So far, many pattern matching algorithms have been proposed. Most of them use single-byte standard unit for search, while a few algorithms such as the Modified Wu-Manber (MWM) algorithm use typically two-byte unit, which guarantees better performance than others even as the number of different signatures increases. Among those algorithms, the MWM algorithm has been known as the fastest pattern matching algorithm when the patterns in a rule set rarely appear in packets. However, the matching time of the MWM algorithm increases as the length of the shortest pattern in a signature group decreases.In this paper, by extending the length of the shortest pattern, we minimize the pattern matching time of the algorithm which uses multi-byte unit. We propose a new pattern matching algorithm called the L⁺¹-MWM algorithm for multi-pattern matching. The proposed algorithm minimizes the performance degradation that is originated from the dependency on the length of the shortest pattern. We show that the L⁺¹-MWM algorithm improves the performance of the MWM algorithm by as much as 20% in average under various lengths of shortest patterns and normal traffic conditions. Moreover, when the length of the shortest pattern in a rule set is less than 5, the L⁺¹-MWM algorithm shows 38.87% enhancement in average. We also conduct experiments on a real campus network and show that 12.48% enhancement is obtained in average. In addition, it is shown that the L⁺¹-MWM algorithm provides a better performance than the MWM algorithm by as much as 25% in average under various numbers of signatures and normal traffic conditions, and 20.12% enhancement in average with real on-line traffic.     

Simultaneous determination of N-acetylcysteine and acetaminophen by voltammetric method using N-(3,4-dihydroxyphenethyl)-3,5-dinitrobenzamide modified multiwall carbon nanotubes paste electrode

A new dopamine-derivative, i.e. N-(3,4-dihydroxyphenethyl)-3,5-dinitrobenzamide (N-DHPB), was synthesized and its application was investigated for the simultaneous determination of N-acetylcysteine (NAC) and acetaminophen (AC) using modified multiwall carbon nanotubes paste electrode. This modified electrode exhibited a potent and persistent electron mediating behavior followed by well separated oxidation peaks of NAC and AC. The peaks current of differential pulse voltammograms of NAC and AC increased linearly with their concentration in the ranges of 0.5-200 μmol L⁻¹ NAC and 15.0-270 μmol L⁻¹ AC. The detection limits for NAC and AC were 0.2 μmol L⁻¹ and 10.0 μmol L⁻¹, respectively. The relative standard deviation for seven successive assays of 1.0 and 30.0 μmol L⁻¹ NAC and AC were 1.7% and 2.2%, respectively. The proposed sensor was successfully applied for the determination of NAC in human urine, tablet, and serum samples.     

Improved algorithms for recognizing p-Helly and hereditary p-Helly hypergraphs

A hypergraph H is set of vertices V together with a collection of nonempty subsets of it, called the hyperedges of H. A partial hypergraph of H is a hypergraph whose hyperedges are all hyperedges of H, whereas for V^′⊆V the subhypergraph (induced by V^′) is a hypergraph with vertices V^′ and having as hyperedges the subsets obtained as nonempty intersections of V^′ and each of the hyperedges of H. For p?1 say that H is p-intersecting when every subset formed by p hyperedges of H contain a common vertex. Say that H is p-Helly when every p-intersecting partial hypergraph H^′ of H contains a vertex belonging to all the hyperedges of H^′. A hypergraph is hereditary p-Helly when every (induced) subhypergraph of it is p-Helly. In this paper we describe new characterizations for hereditary p-Helly hypergraphs and discuss the recognition problems for both p-Helly and hereditary p-Helly hypergraphs. The proposed algorithms improve the complexity of the existing recognition algorithms.     

A state-space search approach for optimizing reliability and cost of execution in distributed sensor networks

Sensor networks are increasingly being used for applications which require fast processing of data, such as multimedia processing and collaboration among sensors to relay observed data to a base station (BS). Distributed computing can be used on a sensor network to reduce the completion time of a task (an application) and distribute the energy consumption equitably across all sensors, so that certain sensors do not die out faster than the others. The distribution of task modules to sensors should consider not only the time and energy savings, but must also improve reliability of the entire task execution. We formulate the above as an optimization problem, and use the A^∗$A^{\ast }$ algorithm with improvements to determine an optimal static allocation of modules among a set of sensors. We also suggest a faster algorithm, called the greedy A^∗$A^{\ast }$ algorithm, if a sub-optimal solution is sufficient. Both algorithms have been simulated, and the results have been compared in terms of energy savings, decrease in completion time of the task, and the deviation of the sub-optimal solution from the optimal one. The sub-optimal solution required 8%–35% less computation, at the cost of 2.5%–15% deviation from the optimal solution in terms of average energy spent per sensor node. Both the A^∗$A^{\ast }$ and greedy A^∗$A^{\ast }$ algorithms have been shown to distribute energy consumption more uniformly across sensors than centralized execution. The greedy A^∗$A^{\ast }$ algorithm is found to be scalable, as the number of evaluations in determining the allocation increases linearly with the number of sensors.     

Q-ary search with one lie and bi-interval queries

The following search game is considered: there are two players, say Paul (or questioner) and Carole (or responder). Carole chooses a number x^*∈Sn={1,2,…,n}, Paul has to find the number x^* by asking q-ary bi-interval queries and Carole is allowed to lie at most once throughout the game. The minimum worst-case number LB(n,q,1) of q-ary bi-interval queries necessary to guess the number x^* is determined exactly for all integers n?1 and q?2. It turns out that LB(n,q,1) coincides with the minimum worst-case number L(n,q,1) of arbitrary q-ary queries.     

On the H fixed-lag smoothing: how to exploit the information preview

The problem of the continuous-time H^∞ fixed-lag smoothing over the infinite horizon is studied. The first solution to the problem is derived in terms of one algebraic Riccati equation of the same dimension as in the filtering case and the mechanism by which the performance improvements with respect to the H^∞ filtering occur is clarified. It is shown that the H^∞ smoother exploits the information preview in an “H² manner”.     

L-fuzzy numbers and their properties

In this paper, the notions of L-fuzzy convex sets and L-fuzzy numbers are introduced where L is a completely distributive lattice. The notions of [0, 1]-fuzzy convex sets and [0, 1]-fuzzy numbers are generalized. Furthermore their properties and characterizations are presented in terms of cut sets of L-fuzzy sets.     

Necessary and sufficient conditions for existence of J-spectral factorization for para-Hermitian rational matrix functions

For a para-Hermitian rational matrix function G(λ)=J+C(λI_p−A)⁻¹B, where J=J∗ is invertible, and which has no poles and zeros on the imaginary line, we give necessary and sufficient conditions in terms of A,B,C and J for the existence of a J-spectral factorization, as well as an algorithm to obtain the J-spectral factor in case it exists.     

灰色GM(1,1,t α)模型与自忆性原理的耦合及应用

针对实际工程应用中传统GM(1,1)模型预测的局限性,以含时间幂次项的灰色GM(1,1,tα)模型为基础,构建了灰色GM(1,1,tα)与自忆性原理的耦合预测模型;用动力系统自忆性原理来克服传统灰色模型对初值比较敏感的弱点;将灰色GM(1,1,t2)自忆性模型应用于某沿海高速软土地基沉降的模拟和预测,获得了满意的模拟和预测精度.实验算例表明,所提出的新模型显著地改善了传统灰色预测模型的模拟预测精度.     

Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.     

Another look at finite horizon H control problems for systems with input delays

We discuss a finite horizon H^∞ control problem for time-varying systems with input delays. Clarifying a relationship between two H^∞ control problems in input delay case and in measurement delay case, we derive a solution in input delay case based on the known result for the H^∞ control problem in measurement delay case, and show that the solution has the same predictor-observer structure as the solution in measurement delay case has. Using this structural information on the solution, we also present an elementary proof of the solution to the finite horizon H^∞ control problem for systems with input delays, which is based only on completion of squares.     

Arithmetic operators in interval-valued fuzzy set theory

We introduce the addition, subtraction, multiplication and division on L^I, where L^I is the underlying lattice of both interval-valued fuzzy set theory [R. Sambuc, Fonctions Φ-floues. Application à l’aide au diagnostic en pathologie thyroidienne, Ph.D. Thesis, Université de Marseille, France, 1975] and intuitionistic fuzzy set theory [K.T. Atanassov, Intuitionistic fuzzy sets, 1983, VII ITKR’s Session, Sofia (deposed in Central Sci. Technical Library of Bulg. Acad. of Sci., 1697/84) (in Bulgarian)]. We investigate some algebraic properties of these operators. We show that using these operators the pseudo-t-representable extensions of the ?ukasiewicz t-norm and the product t-norm on the unit interval to L^I and some related operators can be written in a similar way as their counterparts on ([0,1],?).     

Computing the λ-covers of a string

Given a string x of length n and an integer constant λ, the λ-Cover Problem is defined to be the identification of all the sets of λ substrings each of equal length that cover x. This problem can be solved by a general algorithm in O(n²) time for constant alphabet size. We also generalize the λ-Cover Problem, whereby a set of λ substrings of different lengths are considered, which can be computed using the general algorithm in O(n²) time.