Algebraic Riccati equation and J-spectral factorization for estimation

In this paper we investigate on the existence of the stabilizing solution of the algebraic Riccati equation (ARE) related to the filtering problem with a prescribed attenuation level γ. It is well known that such a solution exists and is positive definite for γ larger than a certain γ_F and it does not exist for γ smaller than a certain γ₀. We consider the intermediate case γ(γ₀,γ_F] and show that in this interval the stabilizing solution does exist, except for a finite number of values of γ. We show how the solution of the ARE may be employed to obtain a minimum-phase J-spectral factor of the J-spectrum associated with the filtering problem.     

Basic Theory of F-Bounded Quantification

System F-bounded is a second-order typed lambda calculus, where the basic features of object-oriented languages can be naturally modelled. F-bounded extends the better known system F, in a way that provides an immediate solution for the treatment of the so-called “binary methods.” Although more powerful than F and also quite natural, system F-bounded has only been superficially studied from a foundational perspective and many of its essential properties have been conjectured but never proved in the literature. The aim of this paper is to give a solid foundation to F-bounded, by addressing and proving the key properties of the system. In particular, transitivity elimination, completeness of the type checking semi-algorithm, the subject reduction property for βη reduction, conservativity with respect to system F, and antisymmetry of a “full” subsystem are considered, and various possible formulations for system F-bounded are compared. Finally, a semantic interpretation of system F-bounded is presented, based on partial equivalence relations.     

On alpha-adic expansions in Pisot bases

We study α-adic expansions of numbers, that is to say, left infinite representations of numbers in the positional numeration system with the base α, where α is an algebraic conjugate of a Pisot number β. Based on a result of Bertrand and Schmidt, we prove that a number belongs to if and only if it has an eventually periodic α-adic expansion. Then we consider α-adic expansions of elements of the ring when β satisfies the so-called Finiteness property (F). We give two algorithms for computing these expansions — one for positive and one for negative numbers. In the particular case that β is a quadratic Pisot unit satisfying (F), we inspect the unicity and/or multiplicity of α-adic expansions of elements of . We also provide algorithms to generate α-adic expansions of rational numbers in that case.     

Detecting Algebraic Curves in Bad Position

Two affine algebraic curves over the complex numbers are in bad position if they have at least two distinct common points on some vertical line, i.e. for some α  C there are distinctβ₁ , β₂  C such that (α,β₁ ) and (α, β₂) are common points of the curves. We describe a method for detecting this situation and use it to develop an algorithm for finding the common points of two algebraic curves along with their multiplicities. We also give a worst case runtime analysis for the two algorithms and include a brief comparison of the second one with an approach using Gröbner bases.     

An efficient architecture for designing reverse converters based on a general three-moduli set

In this paper, a high-speed, low-cost and efficient design of reverse converter for the general three-moduli set {2^α, 2^β − 1, 2^β + 1} where α < β is presented. The simple proposed architecture consists of a carry save adder (CSA) and a modulo adder. As a result it can be efficiently implemented in VLSI circuits. The values of α and β are set in order to provide the desired dynamic range and also to obtain a balanced moduli set. Based on the above, two new moduli sets {2^n+k, 2²ⁿ − 1, 2²ⁿ + 1} and {2²ⁿ⁻¹, 2²ⁿ⁺¹ − 1, 2²ⁿ⁺¹ + 1}, which are the special cases of the moduli set {2^α, 2^β − 1, 2^β + 1} are proposed. The reverse converters for these new moduli sets are derived from the proposed general architecture with better performance compared to the other reverse converters for moduli sets with similar dynamic range.     

New exact nonlinear filters with large Lie algebras

The ideas previously used (Stochastics. Vol. 5, pp. 65–92, 1981) to construct some finite-dimensional nonlinear filters also yield related new filters of finite dimension with arbitrarily large bases; this is because the finite dimensionality is not destroyed by insertion of noiseless linear differential operations on the observations.In engineering language, the new filters are obtained from the old by smoothing the output through an n-pole linear system before adding observation noise in the usual way; this adds 2n to the Lie algebra dimension. In the simplest case (drift = tanh x, OBSERVATION = x) we put x through a one-pole described by a new variable ζ, and observe ζ + noise instead of x + noise; the new Lie algebra has additional generators ζ and ∂/∂ξ besides the four from the oscillator algebra, to give dimension 6.The filter, which gives a recursive construction of the conditional density, can be ‘derived’ by any of three (here equivalent methods: (i) direct integration of the Kallianpur-Striebel formula as a Gaussian integral; (ii) solution of a parabolic PDE with quadratic potential; and (iii) the Wei-Norman procedure.     

Simultaneously controllable fuzzy matrices

Let F be a set of n × n fuzzy matrices. F is called simultaneously controllable if there exists a permutation matrix P such that for each A ε F, C = [c_ij] = P A P^T satisfies c_ij ≥ c_ji for i > j, where is the max-min composition. In this paper, the necessary and sufficient conditions for a set of n × n fuzzy matrices to be simultaneously controllable will be established. A constructive algorithm which can determine a simultaneously controllable set of n × n fuzzy matrices is presented as well.     

The sample complexity of worst-case identification of FIR linear systems

We consider the problem of identification of linear systems in the presence of measurement noise which is unknown but bounded in magnitude by some δ > 0. We focus on the case of linear systems with a finite impulse response. It is known that the optimal identification error is related (within a factor of 2) to the diameter of a so-called uncertainty set and that the latter diameter is upper-bounded by 2δ, if a sufficiently long identification experiment is performed. We establish that, for any K 1, the minimal length of an identification experiment that is guaranteed to lead to a diameter bounded by 2Kδ behaves like 2^Nf(1/K), when N is large, where N is the length of the impulse response and is a positive function known in closed form. While the framework is entirely deterministic, our results are proved using probabilistic tools.     

Trivial Reals

Solovay showed that there are noncomputable reals α such that H(α n) ≤ H(1ⁿ)+O(1), where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem (which means that our construction of an H-trivial computably enumerable set is a particularly easy, injury-free construction of an incomplete c.e. set). Finally, we relate the H-trivials to other classes of “highly nonrandom” reals that have been previously studied.     

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.     

A Temporal Logic for Proving Properties of Topologically General Executions

We present a generalization of the temporal propositional logic of linear time which is useful for stating and proving properties of the generic execution sequence of a parallel program or a non-deterministic program. The formal system we present is exactly that same as the third of three logics presented by Lehmann and Shelah (Information and Control53, 165–198 (1982)), but we give it a different semantics. The models are tree models of arbitrary size similar to those used in branching time temporal logic. The formulation we use allows us to state properties of the “co-meagre” family of paths, where the term “co-meagre” refers to a set whose complement is of the first category in Baire's classification looking at the set of paths in the model as a metric space. Our system is decidable, sound, and, complete for models of arbitrary size, but it has the finite model property; namely, every sentence having a model has a finite model.     

The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

Distributions having bases which generate finite dimensional Lie algebras

Let X¹,…, X^k be real analytic vector fields on an n-dimensional manifold M, k < n, which are linearly independent at a point p ε M and which, together with their Lie products at p, span the tangent space TM_p. Then X¹,…, X^k form a local basis for a real analytic k-dimensional distribution x→D^k(x)=span{X¹(x),…,X^k(x)}. We study the question of when D^k admits a basis which generates a nilpotent, or solvable (or finite dimensional) Lie algebra. If this is the case the study of affine control systems, or partial differential operators, described via X¹,…, X^k can often be greatly simplified.     

The zero divisor problem of multivariable stochastic adaptive control

Stochastic adaptive minimum variance control algorithms require a division by a function of a recursively computed parameter estimate at each instant of time. In order that the analysis of these algorithms is valid, zero divisions must be events of probability zero. This property is established for the stochastic gradient adaptive control algorithm under the condition that the initial state of the system and all finite segments of its random disturbance process have a joint distribution which is absolutely continuous with respect to Lebesgue measure. This result is deduced from the following general result established in this paper: a non-constant rational function of a finite set of random variables {x₁},x_n} is absolutely continuous with respect to Lebesgue measure if the joint distribution function of {x₁,…,x_n} has this property.     

Filtering of some nonlinear diffusions satisfying the general Bene condition

Under some regularity assumptions and the following generalization of the well-known Bene condition [1]:

Full-size image

, where F(t,z) = g⁻²(t)∫f(t,z)dz, F_t, F_z, F_zz, are partial derivatives of F, we obtain explicit formulas for the unnormalized conditional density q_t(z, x) α Px_t ε dz| y_s, 0 st, where diffusion x_t on R¹ solves x₀ = x, dx_t = [β(t) + α(t)x_t + f(t, x_t] dt + g(t) dw₁, and observation y_t = ∫_o^th(s)x_s ds + ∫_o^t(s) dw_2t, with w = (w₁, w₂) a two-dimensional Wiener process.     

Maximum flow and critical cutset as descriptors of multi-state systems with randomly capacitated components

Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b₁(τ), …, B_n(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation.     

Interaction Nets vs. the ρ-calculus: Introducing Bigraphical Nets

The ρ-calculus generalises both term rewriting and the λ-calculus in a uniform framework. Interaction nets are a form of graph rewriting which proved most successful in understanding the dynamics of the λ-calculus, the prime example being the implementation of optimal β-reduction. It is thus natural to study interaction net encodings of the ρ-calculus as a first step towards the definition of efficient reduction strategies. We give two interaction net encodings which bring a new understanding to the operational semantics of the ρ-calculus; however, these encodings have some drawbacks and to overcome them we introduce bigraphical nets—a new paradigm of computation inspired by Lafont's interactions nets and Milner's bigraphs.