Reflexive transitive invariant relations: A basis for computing loop functions

Invariant assertions play an important role in the analysis and verification of iterative programs. In this paper, we introduce a related but distinct concept, namely that of invariant relation. While invariant assertions are useful to prove the correctness of a loop with respect to a specification (represented by a precondition/ postcondition pair) in Hoare’s logic, invariant relations are useful to derive the function of the loop in Mills’ logic.     

循环程序的界函数合成

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

Wavelet approximation-based affine invariant shape representation functions

In this paper, new wavelet-based affine invariant functions for shape representation are presented. Unlike the previous representation functions, only the approximation coefficients are used to obtain the proposed functions. One of the derived functions is computed by applying a single wavelet transform; the other function is calculated by applying two different wavelet transforms with two different wavelet families. One drawback of the previously derived detail-based invariant representation functions is that they are sensitive to noise at the finer scale levels, which limits the number of scale levels that can be used. The experimental results in this paper demonstrate that the proposed functions are more stable and less sensitive to noise than the detail-based functions.     

Invariant kernel functions for pattern analysis and machine learning

In many learning problems prior knowledge about pattern variations can be formalized and beneficially incorporated into the analysis system. The corresponding notion of invariance is commonly used in conceptionally different ways. We propose a more distinguishing treatment in particular in the active field of kernel methods for machine learning and pattern analysis. Additionally, the fundamental relation of invariant kernels and traditional invariant pattern analysis by means of invariant representations will be clarified. After addressing these conceptional questions, we focus on practical aspects and present two generic approaches for constructing invariant kernels. The first approach is based on a technique called invariant integration. The second approach builds on invariant distances. In principle, our approaches support general transformations in particular covering discrete and non-group or even an infinite number of pattern-transformations. Additionally, both enable a smooth interpolation between invariant and non-invariant pattern analysis, i.e. they are a covering general framework. The wide applicability and various possible benefits of invariant kernels are demonstrated in different kernel methods. Editor: Phil Long.     

Mathematics for reasoning about loop functions

The criticality of modern software applications, the pervasiveness of malicious code concerns, the emergence of third-party software development, and the preponderance of program inspection as a quality assurance method all place a great premium on the ability to analyze programs and derive their function in all circumstances of use and all its functional detail. For C-like programming languages, one of the most challenging tasks in this endeavor is the derivation of loop functions. In this paper, we outline the premises of our approach to this problem, present some mathematical results, and discuss how these results can be used as a basis for building an automated tool that derives the function of while loops under some conditions.     

Computationally efficient wavelet affine invariant functions for shape recognition

An affine invariant function for object recognition is constructed from wavelet coefficients of the object boundary. In previous works, undecimated dyadic wavelet transform was used to construct affine invariant functions. In this paper, an algorithm based on decimated wavelet transform is developed to compute an affine invariant function. As a result computational complexity is reduced without decreasing recognition performance. Experimental results are presented.     

Closed loop experiment design for linear time invariant dynamical systems via LMIs

All stationary experimental conditions corresponding to a discrete-time linear time-invariant causal internally stable closed loop with real rational system and feedback controller are characterized using the Youla-Kucera parametrization. Finite dimensional parametrizations of the input spectrum and the Youla-Kucera parameter allow a wide range of closed loop experiment design problems, based on the asymptotic (in the sample size) covariance matrix for the estimated parameters, to be recast as computationally tractable convex optimization problems such as semi-definite programs. In particular, for Box-Jenkins models, a finite dimensional parametrization is provided which is able to generate all possible asymptotic covariance matrices. As a special case, the very common situation of a fixed controller during the identification experiment can be handled and optimal reference signal spectra can be computed subject to closed loop signal constraints. Finally, a brief numerical comparison with closed loop experiment design based on a high model order variance expression is presented.     

New relations between norms of system transfer functions

It is well-known that the H²-norm and H^∞-norm of a transfer function can differ arbitrarily since both norms reflect fundamentally different properties. However, if the pole structure of the transfer function is known it is possible to bound the H^∞-norm from above by a constant multiple of the H²-norm. It is desirable to compute this constant as tightly as possible. In this article we derive a tight bound for the H^∞-norm given knowledge of the H²-norm and the poles of a transfer function. We compute the bound in closed form for multiple input multiple output transfer functions in continuous and discrete time. Furthermore we derive a general procedure to compute the bound given a weighted L²-norm.     

Nonlinear dynamic systems: Their canonical decomposition based on invariant functions

Decomposition of nonlinear dynamic systems based on invariant functions similar to the canonical decomposition of uncontrollable nonobservable linear systems is described.     

On pure,terminal invariant and nonterminal invariant interpretations of EOL forms

This paper (re) considers some basic axioms of the theory of EOL forms. Two new kinds of interpretations are introduced; they form natural steps in-between ordinary and pure interpretations. Various properties of those interpretations are proved and several open problem concerning pure interpretations are solved. In particular certain results are proved which show that synchronized EOL forms have a natural place in the theory of EOL forms (independently of their role as the normal form for EOL systems on language level).     

Atomic functions of three variables invariant with respect to a rotation group

Atomic functions of three variables, i.e., infinitely differentiable compactly supported solutions of functional differential equations of special type are considered. The existence theorem, conclusion about additivity of the function inside the carrier, the probability sense, and the algorithm of calculation of the moments of compactly supported functions are presented.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 118–130, November–December 2004.This revised version was published online in April 2005 with a corrected cover date.     

When QM‐operators are implication functions and conditional fuzzy relations

Some fuzzy reasoning systems base inference processes on fuzzy implication functions. Although there has been a great deal of work done on characterizing R‐ and S‐implications, little is known about QM‐implications in spite of their long history since they came to fuzzy logic by analogy with the quantum mechanic logic. This paper tackles the study of some characteristics of this type of operator. It focuses on the QM‐implication operator both as an implication function and also as a T‐conditional function, giving useful tools to characterize them. © 2000 John Wiley & Sons, Inc.     

A model of invariant object recognition in the visual system: learning rules, activation functions, lateral inhibition, and information-based performance measures

VisNet2 is a model to investigate some aspects of invariant visual object recognition in the primate visual system. It is a four-layer feedforward network with convergence to each part of a layer from a small region of the preceding layer, with competition between the neurons within a layer and with a trace learning rule to help it learn transform invariance. The trace rule is a modified Hebbian rule, which modifies synaptic weights according to both the current firing rates and the firing rates to recently seen stimuli. This enables neurons to learn to respond similarly to the gradually transforming inputs it receives, which over the short term are likely to be about the same object, given the statistics of normal visual inputs. First, we introduce for VisNet2 both single-neuron and multiple-neuron information-theoretic measures of its ability to respond to transformed stimuli. Second, using these measures, we show that quantitatively resetting the trace between stimuli is not necessary for good performance. Third, it is shown that the sigmoid activation functions used in VisNet2, which allow the sparseness of the representation to be controlled, allow good performance when using sparse distributed representations. Fourth, it is shown that VisNet2 operates well with medium-range lateral inhibition with a radius in the same order of size as the region of the preceding layer from which neurons receive inputs. Fifth, in an investigation of different learning rules for learning transform invariance, it is shown that VisNet2 operates better with a trace rule that incorporates in the trace only activity from the preceding presentations of a given stimulus, with no contribution to the trace from the current presentation, and that this is related to temporal difference learning.     

Conditioned invariant and locally conditioned invariant distributions

We define the concepts of conditioned invariant and locally conditioned invariant distributions for nonlinear system and show how they can be used to solve the problem of tracking an output signal of a nonlinear system in spite of unknown disturbances.     

Discrete-time loop transfer recovery via generalized sampled-data hold functions based compensator

Loop transfer recovery (LTR) techniques are known to enhance the input or output robustness properties of linear quadratic gaussian (LQG) designs. One restriction of the existing discrete-time LQG/LTR methods is that they can obtain arbitrarily good recovery only for minimum-phase plants. A number of researchers have attempted to devise new techniques to cope with non-minimum-phase plants and have achieved some degrees of success.^6-9 Nevertheless, their methods only work for a restricted class of non-minimum-phase systems. Here, we explore the zero placement capability of generalized sampled-data hold functions (GSHF) developed in Reference 14 and show that using the arbitrary zero placement capability of GSHF, the discretized plant can always be made minimum-phase. As a consequence, we are able to achieve discrete-time perfect recovery using a GSHF-based compensator irrespective of whether the underlying continuous-time plant is minimum-phase or not.     

Unprejudiced optimal open loop input design for identification of transfer functions

The problem to estimate transfer functions of linear systems is considered. The quality of the resulting estimate depends, among other things, on the input used during the identification experiment. We measure the quality using a quadratic norm in the frequency domain. The problem to determine optimal inputs, i.e. inputs that minimize the chosen norm, subject to constrained input variance, has long been studied. We point out that such procedures may involve a prejudice (that the system is to be found in a certain model set) that may have some surprising effects. We discuss how such a prejudice can be reduced by allowing the possibility that the true system cannot be exactly described in the chosen model set. We also calculate explicit expressions for the resulting “unprejudiced” optimal inputs. These expressions relate the signal-to-noise ratio (as a function of frequency) to the chosen weighting function in the quadratic norm. We also point out the role of the employed noise model for the design.