含区间时变时滞的线性不确定系统鲁棒稳定性新判据

研究一类区间时变时滞线性不确定系统的鲁棒稳定性问题.通过引入增广Lyapunov泛函,结合积分不等式方法,导出了区间时变时滞线性系统的时滞相关鲁棒稳定性新判据.与现有方法不同,该方法不涉及自由权矩阵技术和任何模型变换,减少了理论和计算上的复杂性,而且在估计Lyapunov泛函导数的上界时没有忽略某些有用项.数值算例表明,所提出的判据是有效的,具有更低的保守性.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

A robust optimization approach for imprecise data envelopment analysis

Crisp input and output data are fundamentally indispensable in traditional data envelopment analysis (DEA). However, the input and output data in real-world problems are often imprecise or ambiguous. Some researchers have proposed interval DEA (IDEA) and fuzzy DEA (FDEA) to deal with imprecise and ambiguous data in DEA. Nevertheless, many real-life problems use linguistic data that cannot be used as interval data and a large number of input variables in fuzzy logic could result in a significant number of rules that are needed to specify a dynamic model. In this paper, we propose an adaptation of the standard DEA under conditions of uncertainty. The proposed approach is based on a robust optimization model in which the input and output parameters are constrained to be within an uncertainty set with additional constraints based on the worst case solution with respect to the uncertainty set. Our robust DEA (RDEA) model seeks to maximize efficiency (similar to standard DEA) but under the assumption of a worst case efficiency defied by the uncertainty set and it’s supporting constraint. A Monte-Carlo simulation is used to compute the conformity of the rankings in the RDEA model. The contribution of this paper is fourfold: (1) we consider ambiguous, uncertain and imprecise input and output data in DEA; (2) we address the gap in the imprecise DEA literature for problems not suitable or difficult to model with interval or fuzzy representations; (3) we propose a robust optimization model in which the input and output parameters are constrained to be within an uncertainty set with additional constraints based on the worst case solution with respect to the uncertainty set; and (4) we use Monte-Carlo simulation to specify a range of Gamma in which the rankings of the DMUs occur with high probability.     

Note on “The induced continuous ordered weighted geometric operators and their application in group decision making”

In this short communication, we will show that the condition of the theorem does not hold in general cases in a recent paper “The induced continuous ordered weighted geometric operators and their application in group decision making” [Computers & Industrial Engineering 56 (2009) 1545–1552] by Wu et al., and also illustrate an example to show that we cannot construct a consistent interval multiplicative preference relation according to the condition of theorem in general case. Furthermore, we present a more reasonable condition to satisfy Theorem 1 so that we can construct a consistent interval multiplicative preference relation.     

一种应用主机访问图的网络漏洞评估模型

针对基于攻击图的风险评估的可扩展性问题,从内部安全威胁的角度,提出一种基于主机访问图的漏洞评估的定量方法.首先引入网络访问关系与主机关键度的概念,并提出主机安全威胁模型,接着通过生成主机访问图得到所有主机之间的网络访问关系,在此基础上计算各个漏洞对整个网络安全威胁产生的影响,从而实现对漏洞的评估与排序.实验表明该方法能够有效地评估网络的安全状态和漏洞在网络中的严重程度,并为加强网络安全提供重要依据.     

On the number of higher order Delaunay triangulations

Higher order Delaunay triangulations are a generalization of the Delaunay triangulation that provides a class of well-shaped triangulations, over which extra criteria can be optimized. A triangulation is order-k Delaunay if the circumcircle of each triangle of the triangulation contains at most k points. In this paper we study lower and upper bounds on the number of higher order Delaunay triangulations, as well as their expected number for randomly distributed points. We show that arbitrarily large point sets can have a single higher order Delaunay triangulation, even for large orders, whereas for first order Delaunay triangulations, the maximum number is 2ⁿ⁻³. Next we show that uniformly distributed points have an expected number of at least 2^{ρ₁n(1+o(1))} first order Delaunay triangulations, where ρ₁ is an analytically defined constant (ρ₁≈0.525785), and for k>1, the expected number of order-k Delaunay triangulations (which are not order-i for any i<k) is at least 2^{ρ_kn(1+o(1))}, where ρ_k can be calculated numerically.     

An inexact fuzzy-queue programming model for environmental systems planning

In this study, an inexact fuzzy-queue programming (IFQP) model is developed for municipal solid waste (MSW) management under uncertainty, where fuzzy queue (FQ) model is introduced into the interval-fuzzy linear programming (IFLP) framework. The proposed IFQP model can not only handle uncertainties that are presented in terms of fuzzy sets and discrete intervals, but also reflect the influence of FQ in decision-making problems. Moreover, it can help quantify the satisfaction degrees of the system cost and constraints under uncertainty. It improves upon the existing optimization model with advantages in data availability, uncertainty reflection and result analysis. In its solution process, the model is transformed into two deterministic submodels based on an interactive algorithm. Interval solutions which are stable in the decision space can be obtained by solving the two submodels sequentially. The developed model is applied to a case of long-term planning of MSW management systems to demonstrate its applicability. It can effectively reflect dynamic, interactive, and uncertain characteristics of municipal waste management systems. The decision variable solutions provide optimal schemes for waste flow allocation corresponding to lower and upper bounds of system cost. The results indicate that reasonable solutions have been generated. They are helpful for supporting: (i) decision making or justification of waste-allocation patterns of MSW management system, and (ii) in-depth analysis of tradeoffs among system cost, satisfaction degree, and environmental constraint under uncertainty.     

A 1-Local Asymptotic 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs

In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local asymptotic 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case of hexagonal graph. Based on this result, we then propose a 1-local asymptotic13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm. A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), LNCS 4598, pp. 526–536. Y. Zhang research was supported by European Regional Development Fund (ERDF). F.Y.L. Chin research was supported by Hong Kong RGC Grant HKU-7113/07E. H. Zhu research was supported by National Natural Science Fund (grant #60496321).     

Axiom-based ontology matching

Abstract: Managing multiple ontologies is now a core question in most of the applications that require semantic interoperability. The semantic web is surely the most significant application of this report: the current challenge is not to design, develop and deploy domain ontologies but to define semantic correspondences among multiple ontologies covering overlapping domains. In this paper, we introduce a new approach of ontology matching named axiom-based ontology matching. As this approach is founded on the use of axioms, it is mainly dedicated to heavyweight ontologies, but it can also be applied to lightweight ontologies as a complementary approach to the current techniques based on the analysis of natural language expressions, instances and/or taxonomical structures of ontologies. This new matching paradigm is defined in the context of the conceptual graphs model, where the projection (i.e. the main operator for reasoning with conceptual graphs which corresponds to homomorphism of graphs) is used as a means to semantically match the concepts and the relations of two ontologies through the explicit representation of the axioms in terms of conceptual graphs. We also introduce an ontology of representation, called MetaOCGL, dedicated to the reasoning of heavyweight ontologies at the meta-level.