Decidable containment of recursive queries

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound.     

Combinator-based compilation of recursive functions with different parameter passing modes

Summary Wand's technique of deriving compilers from denotational semantics is applied to a block structured language with recursive functions. The emphasis is on compilation of different parameter passing modes and a simple storage management. The technique starts by eliminating -variables from semantic equations through the introduction of special-purpose combinators. The final code consists of combinators equivalent to target-machine instructions (running-system procedures). The method enables us to derive a compiler and a running system directly from the denotational semantics of a language.     

Optimum recursive filtering of noisy two-dimensional data with sequential parameter identification

A two-dimensional recursive estimation algorithm based on the asymmetric half-plane model is described for the problem of MMSE (minimum mean-square error) filtering. The optimum filtering problem is solved by formulating the asymmetric half-plane ARMA (autoregressive moving average) model for two-dimensional data. The sequential parameter identification from the noisy two-dimensional data is also discussed, utilizing the stochastic approximation. Experiments were performed for real image data, combining the proposed parameter identification and estimation algorithms. The results show that this method gives considerable improvement in SNR.     

Decidable and undecidable logics with a binary modality

We give an overview of decidability results for modal logics having a binary modality. We put an emphasis on the demonstration of proof-techniques, and hope that this will also help in finding the borderlines between decidable and undecidable fragments of usual first-order logic.Research supported by the Hungarian National Foundation for Scientific Research grants no. T16448, F17452, T7255. Research of the first author is also supported by a grant of Logic Graduate School of Eötvös Loránd University Budapest     

Theoretical properties of recursive neural networks with linearneurons

Recursive neural networks are a powerful tool for processing structured data, thus filling the gap between connectionism, which is usually related to poorly organized data, and a great variety of real-world problems, where the information is naturally encoded in the relationships among the basic entities. In this paper, some theoretical results about linear recursive neural networks are presented that allow one to establish conditions on their dynamical properties and their capability to encode and classify structured information. A lot of the limitations of the linear model, intrinsically related to recursive processing, are inherited by the general model, thus establishing their computational capabilities and range of applicability. As a byproduct of our study some connections with the classical linear system theory are given where the processing is extended from sequences to graphs.     

Consistent recursive parameter estimation of partial differential equation models

This article introduces a new residual-based recursive parameter estimation algorithm for linear partial differential equations. The main idea is to replace the unmeasurable noise variables by estimates of the noise and to compute recursively both the model parameters and the noise estimates. It is proven that under some mild assumptions the estimated parameters converge to the true values with probability one. Numerical examples that demonstrate the effectiveness of the proposed approach are also provided.     

Stability of a Riccati equation arising in recursive parameter estimation under lack of excitation

Stability properties of the Riccati equation in a recently suggested antiwindup algorithm for recursive parameter estimation are analyzed. Convergence of the resulting dynamic system is implied by that of a linear time-varying difference matrix equation. By means of converging matrix products theory, the linear mapping associated with the system is shown to be a paracontraction with respect to a certain norm. Therefore, measured in that norm, the solution to the matrix equation will not diverge notwithstanding excitation properties of the data. Thus the purpose of anti-windup is achieved.     

Auto-SOM: recursive parameter estimation for guidance of self-organizing feature maps

An important technique for exploratory data analysis is to form a mapping from the high-dimensional data space to a low-dimensional representation space such that neighborhoods are preserved. A popular method for achieving this is Kohonen's self-organizing map (SOM) algorithm. However, in its original form, this requires the user to choose the values of several parameters heuristically to achieve good performance. Here we present the Auto-SOM, an algorithm that estimates the learning parameters during the training of SOMs automatically. The application of Auto-SOM provides the facility to avoid neighborhood violations up to a user-defined degree in either mapping direction. Auto-SOM consists of a Kalman filter implementation of the SOM coupled with a recursive parameter estimation method. The Kalman filter trains the neurons' weights with estimated learning coefficients so as to minimize the variance of the estimation error. The recursive parameter estimation method estimates the width of the neighborhood function by minimizing the prediction error variance of the Kalman filter. In addition, the "topographic function" is incorporated to measure neighborhood violations and prevent the map's converging to configurations with neighborhood violations. It is demonstrated that neighborhoods can be preserved in both mapping directions as desired for dimension-reducing applications. The development of neighborhood-preserving maps and their convergence behavior is demonstrated by three examples accounting for the basic applications of self-organizing feature maps.     

Formalization of properties of nondeterministic recursive definitions

This paper is concerned with the relationship between the correctness and equivalence of nondeterministic recursive definitions and the satisfiability or validity of certain first-order formulas. Our results suggest some general mathematical techniques useful in verifying the properties of nondeterministic recursive programs.     

Code generation with a recursive optimizer

This paper describes a general purpose optimizer used to construct a new code generator for an existing Coral 66 compiler. The optimizer is recursive and gives the one pass code generator some of the advantages of a multiple pass scheme by ‘pipelining’ short sequences of linear intermediate code at each activation level.     

Stability properties of labeling recursive auto-associative memory

Labeling recursive auto-associative memory (LRAAM) is an extension of the RAAM model by Pollack (1990) to obtain distributed reduced representations of labeled directed graphs. In this paper some mathematical properties of LRAAM are discussed. Specifically, sufficient conditions on the asymptotical stability of the decoding process along a cycle of the encoded structure are given. LRAAM can be transformed into an analog Hopfield network with hidden units and an asymmetric connections matrix by connecting the output units with the input units. In this architecture encoded data can be accessed by content and different access procedures can be defined depending on the access key. Each access procedure corresponds to a particular constrained version of the recurrent network. The authors give sufficient conditions under which the property of asymptotical stability of a fixed point in one particular constrained version of the recurrent network can be extended to related fixed points in different constrained versions of the network. An example of encoding of a labeled directed graph on which the theoretical results are applied is given and discussed.     

Continuous-time constrained least-squares algorithms for recursive parameter estimation of stochastic linear systems by a stabilized output-error method

Discrete-time least-squares algorithms for recursive parameter estimation have continuous-time counterparts, which minimize a quadratic functional. The continuous-time algorithms can also include (in)equality constraints. Asymptotic convergence is demonstrated by means of Lyapunov methods. The constrained algorithms are applied in a stabilized output-error configuration for parameter estimation in stochastic linear systems.     

Stationary behavior of an anti-windup scheme for recursive parameter estimation under lack of excitation

Stationary properties of a recently suggested windup prevention scheme for recursive parameter estimation are investigated in the case of insufficient excitation. When the regressor vector contains data covering the whole parameter space, the algorithm has only one stationary point, the one defined by a weighting matrix. If the excitation is insufficient, the algorithm is shown to possess a manifold of stationary points and a complete parametrization of this manifold is given. However, if the past excitation conditions already caused the algorithm to converge to a certain point, the stationary solution would not be affected by current lack of excitation. This property guarantees good anti-windup properties of the studied parameter estimation algorithm.     

Some properties of the canonical parameter space

The canonical parameter space is symmetric. This simple result is used to extend several theorems on root location involving polynomials where only one class of polynomials is given. The smallest region containing polynomials with largest absolute-value zero of unity or less is derived. This leads to a simple proof for the strongest sufficient condition for the stability of linear discrete-time systems using absolute norms.