Adaptive classification of temporal signals in fixed-weight recurrent neural networks: an existence proof.

Recurrent neural networks with fixed weights have been shown in practice to successfully classify adaptively signals that vary as a function of time in the presence of additive noise and parametric perturbations. We address the question: Can this ability be explained theoretically? We provide a mathematical proof that these networks have this ability even when parametric perturbations enter the signals nonlinearly. The restrictions that we impose on the signals to be classified are that they satisfy an assumption of nondegeneracy and that noise amplitude is sufficiently small. Further, we demonstrate that the recurrent neural networks may not only classify uncertain signals adaptively but also can recover the values of uncertain parameters of the signals, up to their equivalence classes.     

A language-independent proof system for full program equivalence

Two programs are fully equivalent if, for the same input, either they both diverge or they both terminate with the same result. Full equivalence is an adequate notion of equivalence for programs written in deterministic languages. It is useful in many contexts, such as capturing the correctness of program transformations within the same language, or capturing the correctness of compilers between two different languages. In this paper we introduce a language-independent proof system for full equivalence, which is parametric in the operational semantics of two languages and in a state-similarity relation. The proof system is sound: a proof tree establishes the full equivalence of the programs given to it as input. We illustrate it on two programs in two different languages (an imperative one and a functional one), that both compute the Collatz sequence. The Collatz sequence is an interesting case study since it is not known whether the sequence terminates or not; nevertheless, our proof system shows that the two programs are fully equivalent (even if we cannot establish termination or divergence of either one).     

Deforestation, program transformation, and cut-elimination

The problem of proving that two programs, in any reasonable programming language, are equivalent is well-known to be undecidable. In a formal programming system, in which the rules for equivalence are finitely presented, the problem of provable equivalence is semi-decidable. Despite this improved situation there is a significant lack of generally accepted automated techniques for systematically searching for a proof (or disproof) of program equivalence. Techniques for searching for proofs of equivalence often stumble on the formulation of induction and, of course, coinduction (when it is present) which are often formulated in such a manner as to require inspired guesses.There are, however, well-known program transformation techniques which do address these issues. Of particular interest to this paper are the deforestation techniques introduced by Phil Wadler and the fold/unfold program transformation techniques introduced by Burstall and Darlington. These techniques are shadows of an underlying cut-elimination procedure and, as such, should be more generally recognized as proof techniques.In this paper we show that these techniques apply to languages which have both inductive and coinductive datatypes. The relationship between these program transformation techniques and cut-elimination requires a transformation from initial and final “algebra” proof rules into “circular” proof rules as introduced by Santocanale (and used implicitly in the model checking community). This transformation is only possible in certain proof systems. Here we show that it can be applied to cartesian closed categories with datatypes: closedness is an essential requirement. The cut-elimination theorems and attendant program transformation techniques presented here rely heavily on this alternate presentation of induction and coinduction.     

On equivalence of grammars through transformation trees

One approach to solving the equivalence problem for certain families of context free languages is through the use of ‘transformation trees’. We explore this approach in general. The methods developed provide a clear and complete proof of the decidability of the equivalence problem for ‘simple’ languages. It is shown how to decide the equivalence problem for two deterministic context free languages, one of which is simple.     

A residualizing semantics for the partial evaluation of functional logic programs

Recent proposals for multi-paradigm declarative programming combine the most important features of functional, logic and concurrent programming into a single framework. The operational semantics of these languages is usually based on a combination of narrowing and residuation. In this paper, we introduce a non-standard, residualizing semantics for multi-paradigm declarative programs and prove its equivalence with a standard operational semantics. Our residualizing semantics is particularly relevant within the area of program transformation where it is useful, e.g., to perform computations during partial evaluation. Thus, the proof of equivalence is a crucial result to demonstrate the correctness of (existing) partial evaluation schemes.     

A proof–theoretic study of the correspondence of hybrid logic and classical logic

In this paper, we show the equivalence between the provability of a proof system of basic hybrid logic and that of translated formulas of the classical predicate logic with equality and explicit substitution by a purely proof–theoretic method. Then we show the equivalence of two groups of proof systems of hybrid logic: the group of labelled deduction systems and the group of modal logic-based systems.     

Design and Analysis of a Novel ${cal L}_1$ Adaptive Control Architecture With Guaranteed Transient Performance

This paper presents a novel adaptive control architecture that adapts fast and ensures uniformly bounded transient response for system's both signals, input and output, simultaneously. This new architecture has a low-pass filter in the feedback loop and relies on the small-gain theorem for the proof of asymptotic stability. The tools from this paper can be used to develop a theoretically justified verification and validation framework for adaptive systems. Simulations illustrate the theoretical findings.     

Refusal testing

When manipulating concurrent processes it is desirable to suppress their internal details and to consider two processes to be equivalent if their external behaviours are equivalent. Following Milner and De Nicola & Hennessy we take this external equivalence to mean that an observer cannot tell the processes apart by testing their responses to the same stimuli. We introduce a form of testing (refusal testing) which is more powerful than that of De Nicola & Hennessy in that the observer not only tests whether a process will perform an action but is also allowed under certain circumstances to discover in a finite amount of time that the process will not perform an action. The equivalence associated with refusal testing is compared with De Nicola & Hennessy's testing equivalence and Milner's observation equivalence, and a sound and complete proof system is provided for refusal equivalence when applied to CCS processes.     

On some decidable properties of finite state translations

Summary In this paper we present algorithms to decide: 1) single-valuedness of nondeterministic finite transducers, 2) equivalence of single-valued transducers, and 3) whether a given nondeterministic finite transduction can be realized by a deterministic transducer. When such a deterministic realization is possible our proof gives an effective construction of the deterministic transducer.The decidability of single-valuedness and equivalence for a-transducers has been obtained independently by Blattner and Head [3]. Our results introduce different characterizations for decidability and use a different proof that is interesting on its own.We began this research by generalizing the results about decoding automata presented in [5]. A report of these results with a heavy emphasis placed on applications to crytography appears in [6]. This paper presents results applicable in the more general area of finite state translations.     

Equivalence between two solvability conditions for a static output feedback problem

The paper is devoted to providing a proof for showing the equivalence of solvability conditions proposed in Galimidi and Barmish (1986) and Gu (1990) for a static output feedback problem.     

Equivalence of the Gries and Martin proof rules for procedure calls

Summary In this note we prove the equivalence of the proof rules for procedure calls as given by D. Gries [1] and A.J. Martin [2]. We also discuss a modification of these proof rules for the case that the specification of a procedure contains free constants.     

等价闭包矩阵及其算法

1 引言在模糊聚类分析的研究与应用中,基于模糊关系等价闭包的模糊聚类算法,又称等价闭包法是一种重要的方法。等价闭包法即是利用样本间的模糊相似关系矩阵进行模糊矩阵相乘得到模糊等价矩阵进而得到等价闭包矩阵,选取适当的阈值对闭包矩阵截取得到一定的分类。该算法的关键问题就是计算出等价闭包矩阵。设R为模糊相似矩阵,其等价闭包矩阵由下式计算:     

Modular correctness proofs of behavioural implementations

We introduce a concept of behavioural implementation for algebraic specifications which is based on an indistinguishability relation (called behavioural equality). The central objective of this work is the investigation of proof rules which allow us to establish the correctness of behavioural implementations in a modular (and stepwise) way and, moreover, are practicable enough to induce proof obligations that can be discharged with existing theorem provers. Under certain conditions our proof technique can also be applied for proving the correctness of implementations based on an abstraction equivalence between algebras in the sense of Sannella and Tarlecki. The whole approach is presented in the framework of total algebras and first-order logic with equality. Received: 14 August 1995 / 1 April 1998     

基于无迹卡尔曼滤波器的改进SLAM问题求解方法

目前在即时定位与地图构建（Simultaneous Localization And Mapping,SLAM）的研究中已经使用局部取样策略来降低无迹卡尔曼滤波（Unscented Kalman Filter,UKF）的计算复杂度至状态向量维数的平方等级.但是在大规模的SLAM中平方复杂度仍然难以满足实时性需求.为了解决这个问题,提出了一种收缩无迹卡尔曼滤波器（Shrink Unscented Kalman Filter,S-UKF）,并应用于SLAM问题中.首先证明了解耦非线性系统中的部分取样策略和全取样策略的等价性.然后提出了一个通过重构公式中相关项的收缩方式来降低计算复杂度.最后,仿真实验的结果和基于真实环境数据集的实验结果证明了该方法的有效性.     

Using bisimulation proof techniques for the analysis of distributed abstract machines

We illustrate the use of recently developed proof techniques for weak bisimulation by analysing a generic framework for the definition of distributed abstract machines based on a message-passing implementation. We first define this framework, and then focus on the algorithm which is used to route messages asynchronously to their destination.A first version of this algorithm can be analysed using the standard bisimulation up to expansion proof technique. We show that in a second, optimised version, rather complex behaviours appear, for which more sophisticated techniques, relying on termination arguments, are necessary to establish behavioural equivalence.     

Root Images of Median Filters

Median filters are frequently used in signal analysis because of their smoothing properties and their insensitivity with respect to outliers in the data. Since median filters are nonlinear filters, the tools of linear theory are not applicable to them. One approach to deal with nonlinear filters consists in investigating their root images (fixed elements or signals transparent to the filter). Whereas for one-dimensional median filters the set of all root signals can be completely characterized, this is not true for higher dimensional filters.In 1989, Döhler stated a result on certain root images for two-dimensional median filters. Although Döhlers results are true for a wide class of median filters, his arguments were not correct and his assertions do not hold universally. In this paper we give a rigorous proof of Döhlers results. Moreover, his approach is generalized to the d-dimensional case.     

MEASUREMENT THEORY AND SIGNAL THEORY Part II. The Analysis of Digitized Signals

The relation between the continuum theory of matter and the concept of a sensor (measuring instrument) with finite resolution is described. Repeatability of an experiment, equivalence or instruments and refinement of instruments are described in procedural form and with help of simple mathematical tools for both deterministic and non-deterministic signals. Formulae are presented that relate the sampling frequency to the number of samples, and the number of digits per measurement. The attenuation characteristic and the cutoff frequency of a low-pass filter are taken into account. The finite discrete Fourier transform appears to be an adequate tool for signal analysis, which follows from a discussion of the estimation of variance, spectrum, and correlation function for stationary signals. There is no need to turn back or to refer to the infinite Fourier integral transform on continuous functions. If the number of samples increases indefinitely the sampling frequency approaches that of Nyquist's criterion and Shannon's theorem.     

Inference rules for proving the equivalence of recursive procedures

Inspired by Hoare’s rule for recursive procedures, we present three proof rules for the equivalence between recursive programs. The first rule can be used for proving partial equivalence of programs; the second can be used for proving their mutual termination; the third rule can be used for proving the equivalence of reactive programs. There are various applications to such rules, such as proving equivalence of programs after refactoring and proving backward compatibility.     

关于SVD与PCA等价性的研究

利用矩阵的Frobenius范数对奇异值分解(Singular Value Decomposition，SVD)的正规正交基的最优性给出了一种新的证明，论述了SVD与主成分分析的等价性。