Canonical piecewise-linear networks

In this paper, mapping networks will be considered from the viewpoint of the piecewise-linear (PWL) approximation. The so-called canonical representation plays a kernel role in the PWL representation theory. While this theory has been researched intensively in the contents of mathematics and circuit simulations, little has been seen in the research area about the theoretical aspect of neural networks. This paper modifies this theory and applies it as a mathematical support for mapping networks. The main modification is a "higher-level" generalization of the canonical representation with proofs of its availability in the set of PWL functions. The modified theory will first be used to study the canonical PWL feature of the popular multilayer perceptron-like (MLPL) networks. Second, it will be seen that the generalized canonical representation is itself suitable for a network implementation, which is called the standard canonical PWL network. More generally, the family of (generalized) canonical PWL networks is defined as those which may take the canonical PWL representation as a mathematical model. This family is large and practically meaningful. The standard canonical PWL networks may be taken as representatives in the family. The modification of the PWL representation theory as well as the introduction of this theory in the theoretical study of mapping networks, which provide a new concept of mapping networks, i.e., the canonical PWL network family, may be regarded as the main contributions of the paper.     

Observer design for non-linear systems that are not uniformly observable

The observer design problem is studied for a class of single-output non-linear systems that are not necessarily uniformly observable. In the first part of this paper, the non-linear observer canonical form is generalized to the partial non-linear observer canonical form which is quite similar to the decomposition of a linear system into its observable and unobservable states. A necessary and sufficient condition is given for a non-linear system to be transformable into this canonical form by the change of coordinates. Based on this canonical form, a sufficient condition is given for the existence of observers. In the second part, a high gain observer for a class of non-linear systems that are not uniformly observable will be developed in order to relax the system structure of the partial non-linear observer canonical form. To this end, a new canonical form is proposed that generalizes the canonical form of uniform observability and a sufficient condition is provided based on the proposed canonical form.     

有界闭域上的线性赋值循环终止性分析

对有界闭域上的线性赋值循环程序终止性问题进行研究.利用Jordan 标准型技术将原循环程序的终止性问题约减为终止性等价的具有简单结构的循环程序的终止性问题.证明了当线性迭代映射满足一定条件时,该类循环程序不可终止的充分必要条件是：迭代映射在有界闭域上有不动点或周期轨.     

Basic Results in Automatic Transformations of Shared Memory Parallel Programs into Sequential Programs

We study the problem of developing a set of syntax-driven transformations for automatic translation of shared memory parallel programs into sequential programs. The result is a sequential program that is semantically equivalent to the original program. Consequently, the problem of debugging parallel programs is reduced to the problem of debugging sequential programs. Moreover, the efficiency of parallel programs can be increased by sequentializing code segments that include extra parallelism.The main difficulty in developing such a system is to preserve the fairness property of any actual parallel execution, which states that no process can wait forever unserved. Thus, non termination of the sequential version (namely an infinite loop) is allowed only if there is at least one fair parallel execution that does not halt as well (i.e., a process that executes an infinite loop whose termination is not dependent on any other process).We show that it is sufficient to consider the case of two sequential programs executed in parallel in order to solve the general case. We then describe several types of transformations and check their ability to preserve fairness. The results, with regards to the existence of such a transformation for general parallel programs are not conclusive; however, we do show that restricted cases (which are likely to appear in the reality) can be sequentialized using this set of transformations.     

Termination of nondeterministic quantum programs

We define a language-independent model of nondeterministic quantum programs in which a quantum program consists of a finite set of quantum processes. These processes are represented by quantum Markov chains over the common state space, which formalize the quantum mechanical behaviors of the machine. An execution of a nondeterministic quantum program is modeled by a sequence of actions of individual processes, and at each step of an execution a process is chosen nondeterministically to perform the next action. This execution model formalize the users’ behavior of calling the processes in the classical world. Applying the model to a quantum walk as an instance of physically realizable systems, we describe an execution step by step. A characterization of reachable space and a characterization of diverging states of a nondeterministic quantum program are presented. We establish a zero-one law for termination probability of the states in the reachable space. A combination of these results leads to a necessary and sufficient condition for termination of nondeterministic quantum programs. Based on this condition, an algorithm is found for checking termination of nondeterministic quantum programs within a fixed finite-dimensional state space.     

Propositional semantics for disjunctive logic programs

In this paper we study the properties of the class of head-cycle-free extended disjunctive logic programs (HEDLPs), which includes, as a special case, all nondisjunctive extended logic programs. We show that any propositional HEDLP can be mapped in polynomial time into a propositional theory such that each model of the latter corresponds to an answer set, as defined by stable model semantics, of the former. Using this mapping, we show that many queries over HEDLPs can be determined by solving propositional satisfiability problems. Our mapping has several important implications: It establishes the NP-completeness of this class of disjunctive logic programs; it allows existing algorithms and tractable subsets for the satisfiability problem to be used in logic programming; it facilitates evaluation of the expressive power of disjunctive logic programs; and it leads to the discovery of useful similarities between stable model semantics and Clark's predicate completion.     

A Note on Line Search Termination Criteria for Collinear Scaling Algorithms

Ariyawansa [2] has introduced a line search termination criterion for collinear scaling minimization algorithms. However, he verified that this criterion provides sufficient decrease only in the case of objective functions that satisfy certain strong convexity assumptions. In this paper, we report results of our attempts to relax these assumptions. We present an example of a continuously differentiable, nonconvex function with bounded level sets on which the criterion of Ariyawansa [2] does not provide sufficient decrease. This example indicates that specifying line search termination criteria for collinear scaling algorithms is still an open problem. On a more positive note, we are able to show that the class of objective functions on which the criterion of Ariyawansa [2] provides sufficient decrease can be extended to include convex and strictly pseudo-convex functions. Received December 28, 2001; revised November 6, 2002 Published online: January 16, 2003     

基于典型相关回归的多跳非测距定位方法

多跳非测距定位方法是一种有效的、简单的节点定位方法,然而其一般仅适用于各向同性,节点密集网络。针对在各向异性网络中,多跳非测距定位方法定位性能低的问题,提出了基于典型相关回归非测距定位方法。该方法通过典型相关回归获得节点间跳数与欧氏距离精确的映射模型,并利用该映射获得未知节点到已知节点估计距离。仿真实验表明,该方法与现有算法相比具有更高的定位精度和定位稳定性。     

Integrating relational and object-oriented database systems using a metaclass concept

This paper presents a specific approach of integrating a relational database system into a federated database system. The underlying database integration process consist of three steps: first, the external database systems have to be connected to the integrated database system environment and the external data models have to be mapped into a canonical data model. This step is often called syntactic transformation including structural enrichment and leads to component schemas for each external DBMS. Second, the resulting schemas from the first step are used to construct export schemas which are then integrated into global, individual schemas or views in the third step. In this paper we focus on the first step for relational databases, i.e., the connection of a relational database system and the mapping of the relational model into a canonical data model. We take POSTGRES as the relational database system and the object-oriented federated database system VODAK as the integration platform which provides the open, object-oriented data model as the canonical data model for the integration. We show different variations of mapping the relational model. By exploiting the metaclass concept provided by VML, the modelling language of VODAK, we show how to tailor VML such that the canonical data model meets the requirements of integrating POSTGRES into the global database system VODAK in an efficient way.     

Summarization for termination: no return!

We propose a program analysis method for proving termination of recursive programs. The analysis is based on a reduction of termination to two separate problems: reachability of recursive programs, and termination of non-recursive programs. Our reduction works through a program transformation that modifies the call sites and removes return edges. In the new, non-recursive program, a procedure call may non-deterministically enter the procedure body (which means that it will never return) or apply a summary statement.     

Adapting functional programs to higher order logic

Higher-order logic proof systems combine functional programming with logic, providing functional programmers with a comfortable setting for the formalization of programs, specifications, and proofs. However, a possibly unfamiliar aspect of working in such an environment is that formally establishing program termination is necessary. In many cases, termination can be automatically proved, but there are useful programs that diverge and others that always terminate but have difficult termination proofs. We discuss techniques that support the expression of such programs as logical functions. Electronic Supplementary Material  The online version of this article () contains supplementary material, which is available to authorized users.     

单分支线性约束循环程序的终止性分析

秩函数法是循环终止性分析的主要方法,秩函数的存在表明了循环程序是可终止的.针对单分支线性约束循环程序,提出一种方法对此类循环的终止性进行分析.基于增函数法向空间的计算,该方法将原程序空间上的秩函数计算问题归结为其子空间上的秩函数计算问题.实验结果表明,该方法能有效验证现有文献中大部分循环程序的终止性.     

Symbolic performance modeling of parallel systems

Performance prediction is an important engineering tool that provides valuable feedback on design choices in program synthesis and machine architecture development. We present an analytic performance modeling approach aimed to minimize prediction cost, while providing a prediction accuracy that is sufficient to enable major code and data mapping decisions. Our approach is based on a performance simulation language called PAMELA. Apart from simulation, PAMELA features a symbolic analysis technique that enables PAMELA models to be compiled into symbolic performance models that trade prediction accuracy for the lowest possible solution cost. We demonstrate our approach through a large number of theoretical and practical modeling case studies, including six parallel programs and two distributed-memory machines. The average prediction error of our approach is less than 10 percent, while the average worst-case error is limited to 50 percent. It is shown that this accuracy is sufficient to correctly select the best coding or partitioning strategy. For programs expressed in a high-level, structured programming model, such as data-parallel programs, symbolic performance modeling can be entirely automated. We report on experiments with a PAMELA model generator built within a dataparallel compiler for distributed-memory machines. Our results show that with negligible program annotation, symbolic performance models are automatically compiled in seconds, while their solution cost is in the order of milliseconds.     

Abstract regular (tree) model checking

Regular model checking is a generic technique for verification of infinite-state and/or parametrised systems which uses finite word automata or finite tree automata to finitely represent potentially infinite sets of reachable configurations of the systems being verified. The problems addressed by regular model checking are typically undecidable. In order to facilitate termination in as many cases as possible, acceleration is needed in the incremental computation of the set of reachable configurations in regular model checking. In this work, we describe how various incrementally refinable abstractions on finite (word and tree) automata can be used for this purpose. Moreover, the use of abstraction does not only increase chances of the technique to terminate, but it also significantly reduces the problem of an explosion in the number of states of the automata that are generated by regular model checking. We illustrate the efficiency of abstract regular (tree) model checking in verification of simple systems with various sources of infinity such as unbounded counters, queues, stacks, and parameters. We then show how abstract regular tree model checking can be used for verification of programs manipulating tree-like dynamic data structures. Even more complex data structures can be handled using a suitable tree-like encoding.     

Iterative learning of model reference adaptive controller for uncertain nonlinear systems with only output measurement

In this paper, a model reference adaptive control strategy is used to design an iterative learning controller for a class of repeatable nonlinear systems with uncertain parameters, high relative degree, initial output resetting error, input disturbance and output noise. The class of nonlinear systems should satisfy some differential geometric conditions such that the plant can be transformed via a state transformation into an output feedback canonical form. A suitable error model is derived based on signals filtered from plant input and output. The learning controller compensates for the unknown parameters, uncertainties and nonlinearity via projection type adaptation laws which update control parameters along the iteration domain. It is shown that the internal signals remain bounded for all iterations. The output tracking error will converge to a profile which can be tuned by design parameters and the learning speed is improved if the learning gain is large.     

多区域SAR图像分割的改进水平集方法

由于合成孔径雷达（SAR）图像易受相干斑噪声的影响,光学图像的分割方法并不适用于SAR图像,更不能获得精确的分割结果对比,因此,首先基于GA^0统计模型定义能量映射函数以代替像素值进行后续处理,减小相干斑的影响;其次,使用水平集算法对处理后的图像进行分割处理,选用了一种形式更为简单的水平集函数,并可以较容易地推广到多区域SAR图像分割情况。实验结果表明,该方法可以减少相干斑噪声对SAR图像分割过程的不良影响,具有较好的准确性。     

循环程序的界函数合成

作为循环程序终止性分析的主流方法,当前的秩函数方法大多局限于线性或多项式秩函数的求解.针对循环程序若不存在对应的线性或多项式秩函数,现有秩函数方法就无法证明其终止性的问题,提出一个新的方法来合成给定循环程序对应的界函数.对于给定的循环程序,倘若能找到其界函数,则表明该循环程序是可终止的.首先将界函数的求解问题转化为一个...     

The analytical method to solve nonstationary differential games of pursuit

The game problem of pursuit is studied for dynamic processes evolving under uncertainty and counteraction. The terminal set is supposed to be a cylindrical set-valued mapping. The method of resolving functions is used to establish the sufficient conditions for the game termination in the class of quasi- and stroboscopic strategies for various schemes of the method. The guaranteed times are compared. The results are illustrated using the model with integral control unit and game problems with simple motion.     

Simultaneous state estimation and parameter identification in linear fractional order systems using coloured measurement noise

In the present paper, the identification and estimation problem of a single-input–single-output (SISO) fractional order state-space system will be addressed. A SISO state-space model is considered in which parameters and also state variables should be estimated. The canonical fractional order state-space system will be transformed into a regression equation by using a linear transformation and a shift operator that are appropriate for identification. The identification method provided in this paper is based on a recursive identification algorithm that has the capability of identifying the parameters of fractional order state-space system recursively. Another subject that will be addressed in this paper is a novel fractional order Kalman filter suitable for the systems with coloured measurement noise. The promising performance of the proposed methods is verified using two stable fractional order systems.