An Estimation Problem for Quasilinear Stochastic Partial Differential Equations

A problem of estimating a functional parameter (x) and functionals () based on observation of a solution u (t, x) of the stochastic partial differential equation is considered. The asymptotic problem setting, as the noise intensity 0, is investigated.     

Congruences et Automorphismes des Automates Finis

Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is .     

Concurrent Sample Path Analysis of Discrete Event Systems

The sample path constructability problem for Discrete Event Systems (DES) involves the observation of a sample path under a particular parameter value of the system with the requirement to concurrently construct multiple sample paths of the DES under different values using only information available along the given sample path. This allows the on-line estimation of performance measures , not available in closed form, over a range of values of . We present a sample path coupling approach that solves the problem without imposing any restrictions on the event processes in the system. A specific time warping algorithm is described and its performance is analyzed in terms of computational cost. Our approach is illustrated through a number of simulation results.     

Dynamical Properties of Timed Automata

Timed automata are an important model for specifying and analyzing real-time systems. The main analysis performed on timed automata is the reachability analysis. In this paper we show that the standard approach for performing reachability analysis is not correct when the clocks drift even by a very small amount. Our formulation of the reachability problem for timed automata is as follows: we define the set R ^*(T,Z ₀)=_>0 Reach(T, Z ₀ where T is obtained from timed automaton T by allowing an drift in the clocks. R ^*(T,Z ₀) is the set of states which can be reached in the timed automatonT from the initial states in Z₀ when the clocks drift by an infinitesimally small amount. We present an algorithm for computing R ^*(T,Z ₀)and provide a proof of its correctness. We show that R ^*(T,Z ₀)is robust with respect to various types of modeling errors. To prove the correctness of our algorithm, we need to understand the dynamics of timed automata—in particular, the structure of the limit cycles of timed automata.     

Solving A\underline x =\underline b Using a Modified Conjugate Gradient Method Based on Roots of A

We consider the modified conjugate gradient procedure for solving A = in which the approximation space is based upon the Krylov space associated with A ^1/p and , for any integer p. For the square-root MCG (p=2) we establish a sharpened bound for the error at each iteration via Chebyshev polynomials in . We discuss the implications of the quickly accumulating effect of an error in in the initial stage, and find an error bound even in the presence of such accumulating errors. Although this accumulation of errors may limit the usefulness of this method when is unknown, it may still be successfully applied to a variety of small, almost-SPD problems, and can be used to jump-start the conjugate gradient method. Finally, we verify these theoretical results with numerical tests.     

Biologically Inspired Autonomous Rover Control

Robotic missions beyond 2013 will likely be precursors to a manned habitat deployment on Mars. Such missions require robust control systems for long duration activities. Current single rover missions will evolve into deployment of multiple, heterogeneous cooperating robotic colonies. This paper describes the map-making memory and action selection mechanism of BISMARC ( iologically nspired ystem for ap-based utonomous over ontrol) that is currently under development at the Jet Propulsion Laboratory in Pasadena, CA (Huntsberger and Rose, Neutral Networks, 11(7/8):1497–1510). BISMARC is an integrated control system for long duration missions involving robots performing cooperative tasks.     

An Algebraic Approach to Propositional Fuzzy Logic

We investigate the variety corresponding to a logic (introduced in Esteva and Godo, 1998, and called there), which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative (and slightly simpler) axiomatization of such variety. We also investigate the variety, called the variety of algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that every algebra can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield , and whose operations are the truncations of the operations of to [0, 1]. We prove that such a structure is uniquely determined by up to isomorphism, and we establish an equivalence between the category of algebras and that of f-semifields.     

Error Estimation for Indirect Measurements: Interval Computation Problem Is (Slightly) Harder Than a Similar Probabilistic Computational Problem

One of main applications of interval computations is estimating errors of indirect measurements. A quantity y is measured indirectly if we measure some quantities xi related to y and then estimate y from the results of these measurements as by using a known relation f. Interval computations are used "to find the range of f(x1,...,xn) when xi are known to belong to intervals ," where i are guaranteed accuracies of direct measurements. It is known that the corresponding problem is intractable (NP-hard) even for polynomial functions f.In some real-life situations, we know the probabilities of different value of xi; usually, the errors xi - are independent Gaussian random variables with 0 average and known standard deviations i. For such situations, we can formulate a similar probabilistic problem: "given i, compute the standard deviation of f(x1,...,xn) ." It is reasonably easy to show that this problem is feasible for polynomial functions f. So, for polynomial f, this probabilistic computation problem is easier than the interval computation problem.It is not too much easier: Indeed, polynomials can be described as functions obtained from xi by applying addition, subtraction, and multiplication. A natural expansion is to add division, thus getting rational functions. We prove that for rational functions, the probabilistic computational problem (described above) is NP-hard.     

Exact Linear Thermodynamic Evolution Equations from the Robertson Formalism

A linear evolution equation for a thermodynamic variable F, odd under time-reversal, is obtained from the exact equation derived by Robertson from the Liouville equation for the information-theoretic phase-space distribution. One obtains an exact expression for , the relaxation time for F. For very short , is time-independent for t > if C(t) F{exp(-i t)}Fo, the equilibrium time correlation, decays exponentially for t > . is the Liouville operator. So long as C(t) is such that decays rapidly to a steady-state value, the t limit of agrees with the fluctuation-dissipation theorem in applications to fluid transport.     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

Modelling Asynchrony with a Synchronous Model

The I/O automaton paradigm of Lynch and Tuttle models asynchrony through an interleaving parallel composition. The recognition that such interleaving models in fact can be viewed as special cases of synchronous parallel composition has been very limited. Let be any set of finite-state I/O automata drawing actions from a fixed finite set containing a subset . In this article we establish a translation T : to a class of -automata closed under a synchronous parallel composition, for which T is monotonic with respect to implementation relative to , and linear with respect to composition. Thus, for A¹, ..., A, B¹, ..., B and A = A¹ ... A, B = B¹ ... B, if is the set of actions common to both A and B, then A implements B (in the sense of I/O automata) if and only if the -automaton language containment (T(A¹) ... T(A)) (T(B¹) ... T(B)) obtains, where denotes the interleaving parallel composition on and denotes the synchronous parallel composition on . For the class , we use the L-process model of -automata. This result enables one to verify systems specified by I/O automata through model-checkers such as COSPAN or SMV, that operate on models with synchronous parallel composition. The translation technique generalizes to other interleaving models, although in each case, the translation map must match the specific model.     

Structural properties for feasibly computable classes of type two

This paper treates classes in the polynomial hierarchy of type two, , that were first developed by Townsend as a natural extension of the Meyer-Stockmeyer polynomial hierarchy in complexity theory. For these classes, it is discussed whether each of them has the extension property and the three recursion-theoretic properties: separation, reduction, and pre-wellordering. This paper shows that every 0$$ " align="middle" border="0"> , lacks the pre-wellordering property by using a probabilistic argument on constant-depth Boolean circuits. From the assumption NP = coNP it follows by a pruning argument that has the separation and extension properties.     

Efficient Algorithms for k Maximum Sums

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem involves finding the k largest values of for The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a -time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in time in the worst case. Our algorithm is optimal for and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.     

Decision procedures for elementary sublanguages of set theory

In this paper we prove the decidability of the class of unquantified formulae of set theory involving the operators , , , \, {·}, pred _< and the predicates =, , , Finite, where pred _<(s) denotes the collection of all sets having rank strictly less than the rank of s.This work generalizes and combines earlier results published in the same series of papers.This work has been partially supported by ENI and ENIDATA within the AXL project.     

Exact optimal grillage layouts — Part I: Combinations of free and simply supported edges

In the first instalment of this three-part study, a comprehensive treatment of analytically derived, exact optimal grillage layouts for combinations of simply supported and free edges is given. In part two, grillages with combinations of simply supported, clamped and free edges will be considered.Notation k constant in specific cost function - M beam bending moment - r radius of circular edge - R ⁺,R ^–,S ⁺,S ^–,T optimal regions - x, x _j coordinate along a beam (j) - slope of the adjoint deflection at pointD in directionDA - t, v coordinates along the free edge - adjoint deflection - angle between long beams and free edge - angle between free and simply supported edges - curvature of the adjoint deflection - , angles for layouts with circular edge - total weight (cost) of grillage - coordinate along a beam in anR ⁺ region - distance defined in Fig. 3     

The Complexity of Learning According to Two Models of a Drifting Environment

We show that a bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy , where c > 0 is a constant; this matches a known necessary condition to within a constant factor. We establish a sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor. We provide a relatively simple proof of a bound of + on the sample complexity of agnostic learning in a fixed environment.     

Crash failure detection in asynchronous agent communication languages

Agent Communication Languages (ACLs) have been developed to provide a way for agents to communicate with each other supporting cooperation in Multi-Agent Systems (MAS). In the past few years many ACLs have been proposed for MAS and new standards are emerging such as the ACL developed by the Foundation for Intelligent Physical Agents (FIPA). Despite these efforts, an important issue in the research on ACLs is still open and concerns how these languages should deal with failures of agents in asynchronous MAS. The Fault Tolerant Agent Communication Language ( - ) presented in this paper addresses this issue dealing with crash failures of agents. - provides high-level communication primitives which support a fault-tolerant anonymous interaction protocol designed for open MAS. We present a formal semantics for - and a formal specification of the underlying agent architecture. This formal framework allows us to prove that the ACL satisfies a set of well defined knowledge-level programming requirements. To illustrate the language features we show how - can be effectively used to write high-level executable specifications of fault tolerant protocols, such as the Contract Net one.     

L 1 Sensitivity minimization for plants with commensurate delays

In this paper we consider the problem ofL ¹ sensitivity minimization for linear plants with commensurate input delays. We describe a procedure for computing the minimum performance, and we characterize optimal solutions. The computations involve solving a one-parameter family of finite-dimensional linear programs. Explicit solutions are presented for important special cases.Notation X ^* Dual space of a normed linear spaceX - All elements inS with norm 1 - S The annihilator subspace defined as . - S The annihilator subspace defined as . - BV(X) Functions of bounded variation onX - C ₀(X) Continuous function on a locally compact spaceX such that for all > 0, {x X¦ ¦f(x)¦s is compact - C ^N (a, b) Vectors of continuous functions on (a, b) The authors acknowledge support from the Army Research Office, Center for Intelligent Control, under grant DAAL03-86-K-0171, and the National Science Foundation, under grant 8810178-ECS.     

Conditions for Instability of One Class of Nonlinear Nonautomomous Dynamic Systems

Consideration was given to the conditions for instability of the equilibrium states of a nonlinear nonautonomous dynamic systems obeying an ordinary vector differential equation of arbitrary order whose right-hand side satisfies the following conditions: (i) for any t 0, div 0$$ " align="middle" border="0"> almost everywhere on the set H that is a neighborhood of the equilibrium point of the system and (ii) at any point . The equilibrium states of such systems can be both stable and unstable. For one class of these systems, sufficient instability conditions were given, which enables one to carry out studies using only the information about the right-hand side of the system.