An Extension of System F with Subtyping

System F is a well-known typed λ-calculus with polymorphic types, which provides a basis for polymorphic programming languages. We study an extension of F, called F_<: (pronounced ef-sub), that combines parametric polymorphism with subtyping. The main focus of the paper is the equational theory of F_<:, which is related to PER models and the notion of parametricity. We study some categorical properties of the theory when restricted to closed terms, including interesting categorical isomorphisms. We also investigate proof-theoretical properties, such as the conservativity of typing judgments with respect to F. We demonstrate by a set of examples how a range of constructs may be encoded in F_<:. These include record operations and subtyping hierarchies that are related to features of object-oriented languages.     

Convergent algorithms for frequency weighted L2 model reduction

This paper is concerned with computing an L₂-optimal reduced-order model for a given stable multivariable linear system in the presence of input and output frequency weightings. By parametrizing a class of reduced-order models in terms of an orthogonal projection and using manifold techniques as tools, both continuous and iterative algorithms are derived and their convergence properties are established. As an application, we show that an L₂ optimal reduced-order filter in the closed-loop sense can be computed using these algorithms.     

Bonsai: A compact representation of trees

This paper shows how trees can be stored in a very compact form, called ‘Bonsai’, using hash tables. A method is described that is suitable for large trees that grow monotonically within a predefined maximum size limit. Using it, pointers in any tree can be represented within 6 + [log₂n] bits per node where n is the maximum number of children a node can have. We first describe a general way of storing trees in hash tables, and then introduce the idea of compact hashing which underlies the Bonsai structure. These two techniques are combined to give a compact representation of trees, and a practical methodology is set out to permit the design of these structures. The new representation is compared with two conventional tree implementations in terms of the storage required per node. Examples of programs that must store large trees within a strict maximum size include those that operate on trie structures derived from natural language text. We describe how the Bonsai technique has been applied to the trees that arise in text compression and adaptive prediction, and include a discussion of the design parameters that work well in practice.     

结合限制的分隔模型及K-Means算法

将数据对象间的关联限制与K-means算法结合可以取得较好的效果,但由于划分是由K个中心决定的,每一类仅由一个中心决定,分隔的表示方法限制了算法效果的进一步提高.基于数据对象间的两类限制,定义了数据对象和集合间的两类关联,以及集合间的3类关联,在此基础上给出了结合限制的分隔模型.在模型中,基于集合间的正关联,多个子集中心可以用来表示同一类,使划分的表示可以更为灵活、精细.基于此模型,给出了相应的算法CKS(constrained K-meanswith subsets)来生成结合限制的分隔.对3个UCI数据集的实验结果显示:在准确率及健壮性上,CKS显著优于另一个结合关联限制的K-means类算法COP-K-means,与另一个代表性的算法CCL相比,也有相当优势;在时间代价上,CKS也有一定优势.     

Uq(sl(2)) Satisfies a Bernstein Duality

It is well known that in some cases the functorExt_R^μ( − , R) defines a duality between module categories. In earlier papers we studied when this duality can be represented by a bimodule and have characterized when this happens. In this paper, using some computational methods of noncommutative Gröbner bases in the construction of projective resolutions of irreducible finite-dimensional representations, we show new examples of algebras satisfying this property.     

Inducing Constructor Systems from Example-Terms by Detecting Syntactical Regularities

We present a technique for inducing functional programs from few, well chosen input/output-examples (I/O-examples). Potential applications for automatic program or algorithm induction are to enable end users to create their own simple programs, to assist professional programmers, or to automatically invent completely new and efficient algorithms. In our approach, functional programs are represented as constructor term rewriting systems (CSs) containing recursive rules. I/O-examples for a target function to be implemented are a set of pairs of terms (F(i_i),o_i) meaning that F(i_i)—denoting application of function F to input i_i—is rewritten to o_i by a CS implementing the function F. Induction is based on detecting syntactic regularities between example terms. In this paper we present theoretical results and describe an algorithm for inducing CSs over arbitrary signatures/data types which consist of one function defined by an arbitrary number of rules with an arbitrary number of non-nested recursive calls in each rule. Moreover, we present empirical results based on a prototypical implementation.     

基于XYZ/E描述和验证容错系统

研究使用XYZ/E描述和验证容错系统.基于XYZ/E中可执行程序P对应的状态转换系统对其错误环境F建模,通过错误转换给出错误影响程序P_F;基于P,F和恢复算法R,通过容错转换给出容错程序P_F-R;定义了程序P,Q之间两种求精关系:容错求精和向后恢复求精,基于这两种求精关系可直接从程序P的规范推导出程序Q满足的一些性质.     

H∞ control of a class of 2-D continuous switched delayed systems via state-dependent switching

This paper addresses the problem of state feedback H_∞ stabilisation of 2-D (two-dimensional) continuous switched state delayed systems represented by the Roesser model using the multiple Lyapunov functional approach. First, an asymptotical stability condition of 2-D continuous switched systems with state-dependent switching is derived. Second, a sufficient condition for H_∞ performance of the underlying system is established. Third, a state feedback controller is proposed to ensure that the resulting closed-loop system has a prescribed H_∞ performance level under a state-dependent switching signal. All the results are developed in terms of linear matrix inequalities. Finally, three examples are provided to demonstrate the validity and effectiveness of the proposed method.     

An Algorithm for Finding the K-Best Allocations of a Tree Structured Program

We consider the problem of allocating n tasks of a distributed program to m processors of a distributed system in order to minimize total communication and processing costs. If the intertask communication can be represented by a tree and if the communication costs are uniform, it is known that an optimal allocation can be determined in O(nm) time. A K-optimal solution set Ω = { ₁,..., _K} of a given task allocation problem is a set of allocations such that no allocation which is not contained in Ω is better than any _i, i = 1,..., K. In this paper, an algorithm is presented which computes a K-optimal set for the considered task allocation problem in O(Knm).     

2D Bilinear programming for robust PID/DD controller design

A new design method of PID structured controllers to achieve robust performance is developed. Both robust stabilization and performance conditions are losslessly expressed by bilinear constraints in the proportional‐double derivative variable ( k _P, k _DD) and the integral‐derivative variable ( k _I, k _D). Therefore, the considered control design can be efficiently solved by alternating optimization between ( k _P, k _DD) and ( k _I, k _D), which is a 2D computationally tractable program. The proposed method works equally efficiently whenever even higher order differential or integral terms are included in PID control to improve its robustness and performance. Numerical examples are provided to show the viability of the proposed development. Copyright © 2016 John Wiley & Sons, Ltd.     

Bipartite isoperimetric graph partitioning for data co-clustering

Data co-clustering refers to the problem of simultaneous clustering of two data types. Typically, the data is stored in a contingency or co-occurrence matrix C where rows and columns of the matrix represent the data types to be co-clustered. An entry C _ij of the matrix signifies the relation between the data type represented by row i and column j. Co-clustering is the problem of deriving sub-matrices from the larger data matrix by simultaneously clustering rows and columns of the data matrix. In this paper, we present a novel graph theoretic approach to data co-clustering. The two data types are modeled as the two sets of vertices of a weighted bipartite graph. We then propose Isoperimetric Co-clustering Algorithm (ICA)—a new method for partitioning the bipartite graph. ICA requires a simple solution to a sparse system of linear equations instead of the eigenvalue or SVD problem in the popular spectral co-clustering approach. Our theoretical analysis and extensive experiments performed on publicly available datasets demonstrate the advantages of ICA over other approaches in terms of the quality, efficiency and stability in partitioning the bipartite graph.     

Context-sensitive queries for image retrieval in digital libraries

In this paper we show how to achieve a more effective Query By Example processing, by using active mechanisms of biological vision, such as saccadic eye movements and fixations. In particular, we discuss the way to generate two fixation sequences from a query image I _q and a test image I _t of the data set, respectively, and how to compare the two sequences in order to compute a similarity measure between the two images. Meanwhile, we show how the approach can be used to discover and represent the hidden semantic associations among images, in terms of categories, which in turn drive the query process.     

A novel retrieval approach reflecting variability of syntactic phrase representation

In this paper, we introduce variability of syntactic phrases and propose a new retrieval approach reflecting the variability of syntactic phrase representation. With variability measure of a phrase, we can estimate how likely a phrase in a given query would appear in relevant documents and control the impact of syntactic phrases in a retrieval model. Various experimental results over different types of queries and document collections show that our retrieval model based on variability of syntactic phrases is very effective in terms of retrieval performance, especially for long natural language queries.     

Two-time-scale distributions and singular perturbations

Two-time-scale (TTS) distributions are introduced. For a class of stable systems, it is shown that every TTS distribution has a two-frequency-scale (TFS) Laplace transform. Conversely, it is shown that the impulse response of any stable TFS transfer function, and hence any stable (standard) singularly perturbed system, can be characterized in terms of a stable TTS distribution. A time domain decomposition for TTS distributions is obtained which parallels the slow and fast decomposition of singularly perturbed systems and also the frequency domain decomposition of TFS transfer functions. It is shown that every stable TTS distribution can be decomposed in terms of two simpler distributions represented in two different time scales. A composite distribution is constructed from these two which approximates the TTS distribution arbitrarily closely in the L ₁ norm.     

Takagi–Sugeno Fuzzy Hopfield Neural Networks for $${\mathcal{H}_{\infty}}$$ Nonlinear System Identification

In this paper, we propose a new H_￥{\mathcal H_\infty} weight learning algorithm (HWLA) for nonlinear system identification via Takagi–Sugeno (T–S) fuzzy Hopfield neural networks with time-delay. Based on Lyapunov stability theory, for the first time, the HWLA for nonlinear system identification is presented to reduce the effect of disturbance to an H_￥{\mathcal{H}_{\infty }} norm constraint. The HWLA can be obtained by solving a convex optimization problem which is represented in terms of linear matrix inequality (LMI). An illustrative example is given to demonstrate the effectiveness of the proposed identification scheme.     

TOWARDS A GLOBAL ANALYSIS OF SYSTEMS

In this paper a topological approach to the analysis or properties or systems is outlined and accounted for, which is called a Global Analysis of Systems (GAS). Let a topological space t of system; and a property P of systems from Σ be given. Define Σ _p = {σ∈Σ; σ has the properly P}. Then the main question of the Global Analysis of Systems is: how can Σ _p , be characterized in topological terms? We claim that three types of properties are worthy of being distinguished from this topological point of view. They are called structural, generic and residual properties, if I, appears to be an open, open and dense, and residual subset of I respectively. A motivation for the Global Analysis of Systems flowing from differential geometry, theory of dynamical systems, catastrophe theory and the theory of control systems is presented. In conclusion a significance of the Global Analysis of Systems, both far systems theory and for a better understanding of the fundamental relation Model—Reality, is discussed.     

Timed Modal Logics for Real-Time Systems

In this paper, a timed modal logic L _c is presented for the specification and verification of real-time systems. Several important results for L _c are discussed. First we address the model checking problem and we show that it is an EXPTIME-complete problem. Secondly we consider expressiveness and we explain how to express strong timed bisimilarity and how to build characteristic formulas for timed automata. We also propose a compositional algorithm for L _c model checking. Finally we consider several control problems for which L _c can be used to check controllability.     

H∞ model reduction of Markovian jump linear systems

In this paper, the H_∞ model reduction problem for linear systems that possess randomly jumping parameters is studied. The development includes both the continuous and discrete cases. It is shown that the reduced order models exist if a set of matrix inequalities is feasible. An effective iterative algorithm involving linear matrix inequalities is suggested to solve the matrix inequalities characterizing the model reduction solutions. Using the numerical solutions of the matrix inequalities, the reduced order models can be obtained. An example is given to illustrate the proposed model reduction method.     

CONTROL LAW FOR QUADRATIC STABILIZATION OF PERTURBED FUZZY TIME‐DELAY LARGE‐SCALE SYSTEMS VIA LMI

In this paper, the perturbed continuous‐time large‐scale system with time delays is represented by an equivalent Takagi‐Sugeno type fuzzy model. First, two types of decentralized state feedback controllers are considered in this paper. Based on the Riccati‐type inequality, the Razumikhin theorem, and the delay‐dependent Lyapunov functional approach, some controller design approaches are proposed to stabilize the whole fuzzy time‐delay system asymptotically. In these design methods, both the delay‐independent and delay‐dependent stabilization criteria are derived. By Schur complement, these sufficient conditions can be easily transformed into the problem of LMI's. Moreover, the systems with all the time‐delays τ^l_ij (t) are the same for all rules (i.e., τ^l_ij (t) = τ^m_ij (t) = τ_ij for all l =m); the authors also propose a simpler and less conservative stabilizing criteria. A numerical example is given to illustrate the control design and its effectiveness.