Conflict-directed A and its role in model-based embedded systems

Artificial Intelligence has traditionally used constraint satisfaction and logic to frame a wide range of problems, including planning, diagnosis, cognitive robotics and embedded systems control. However, many decision making problems are now being re-framed as optimization problems, involving a search over a discrete space for the best solution that satisfies a set of constraints. The best methods for finding optimal solutions, such as A^*, explore the space of solutions one state at a time. This paper introduces conflict-directed A^*, a method for solving optimal constraint satisfaction problems. Conflict-directed A^* searches the state space in best first order, but accelerates the search process by eliminating subspaces around each state that are inconsistent. This elimination process builds upon the concepts of conflict and kernel diagnosis used in model-based diagnosis [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(1) (1987) 97-130; J. de Kleer, A. Mackworth, R. Reiter, Characterizing diagnoses and systems, Artif. Intell. 56 (1992) 197-222] and in dependency-directed search [R. Stallman, G.J. Sussman, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artif. Intell. 9 (1977) 135-196; J. Gaschnig, Performance measurement and analysis of certain search algorithms, Technical Report CMU-CS-79-124, Carnegie-Mellon University, Pittsburgh, PA, 1979; J. de Kleer, B.C. Williams, Back to backtracking: controlling the ATMS, in: Proceedings of AAAI-86, 1986, pp. 910-917; M. Ginsberg, Dynamic backtracking, J. Artif. Intell. Res. 1 (1993) 25-46]. Conflict-directed A^* is a fundamental tool for building model-based embedded systems, and has been used to solve a range of problems, including fault isolation [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(1) (1987) 97-130], diagnosis [J. de Kleer, B.C. Williams, Diagnosis with behavioral modes, in: Proceedings of IJCAI-89, 1989, pp. 1324-1330], mode estimation and repair [B.C. Williams, P. Nayak, A model-based approach to reactive self-configuring systems, in: Proceedings of AAAI-96, 1996, pp. 971-978], model-compilation [B.C. Williams, P. Nayak, A reactive planner for a model-based executive, in: Proceedings of IJCAI-97, 1997] and model-based programming [M. Ingham, R. Ragno, B.C. Williams, A reactive model-based programming language for robotic space explorers, in: Proceedings of ISAIRAS-01, 2001].     

The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Convergence of multi-level iterative aggregation–disaggregation methods

This paper introduces an error propagation formula of a certain class of multi-level iterative aggregation–disaggregation (IAD) methods for numerical solutions of stationary probability vectors of discrete finite Markov chains. The formula can be used to investigate convergence by computing the spectral radius of the error propagation matrix for specific Markov chains. Numerical experiments indicate that the same type of the formula could be used for a wider class of the multi-level IAD methods. Using the formula we show that for given data there is no relation between convergence of two-level and of multi-level IAD methods.     

The double exponential map on spaces of constant curvature

In the article, we derive an explicit formula for the double exponential map on spaces of constant curvature. In addition, we consider some applications of the resulting formula to computing the principal symbol of the product of two pseudodifferential operators on a manifold with connection.     

First exit time probability for multidimensional diffusions: A PDE-based approach

First exit time distributions for multidimensional processes are key quantities in many areas of risk management and option pricing. The aim of this paper is to provide a flexible, fast and accurate algorithm for computing the probability of the first exit time from a bounded domain for multidimensional diffusions. First, we show that the probability distribution of this stopping time is the unique (weak) solution of a parabolic initial and boundary value problem. Then, we describe the algorithm which is based on a combination of the sparse tensor product finite element spaces and an hp-discontinuous Galerkin method. We illustrate our approach with several examples. We also compare the numerical results to classical Monte Carlo methods.     

A general composite explicit iterative scheme of fixed point solutions of variational inequalities for nonexpansive semigroups

In this paper, we introduce a composite explicit viscosity iteration method of fixed point solutions of variational inequalities for nonexpansive semigroups in Hilbert spaces. We prove strong convergence theorems of the composite iterative schemes which solve some variational inequalities under some appropriate conditions. Our result extends and improves those announced by Li et al [General iterative methods for a one-parameter nonexpansive semigroup in Hilbert spaces, Nonlinear Anal. 70 (2009) 3065–3071], Plubtieng and Punpaeng [S. Plubtieng, R. Punpaeng, Fixed-point solutions of variational inequalities for nonexpansive semigroups in Hilbert spaces, Math. Comput. Modelling 48 (2008) 279–286], Plubtieng and Wangkeeree [S. Plubtieng, R. Wangkeeree, A general viscosity approximation method of fixed point solutions of variational inequalities for nonexpansive semigroups in Hilbert spaces, Bull. Korean Math. Soc. 45 (4) (2008) 717–728] and many others.     

A Cheaper Way to Compute Generalized Cross-Validation as a Stopping Rule for Linear Stationary Iterative Methods

We apply generalized cross-validation (GCV) as a stopping rule for general linear stationary iterative methods for solving very large-scale, ill-conditioned problems. We present a new general formula for the influence operator for these methods and, using this formula and a Monte Carlo approach, we show how to compute the GCV function at a cheaper cost. Then we apply our approach to a well known iterative method (ART) with simulated data in positron emission tomography (PET).     

Computing rotation and self-linking numbers in contact surgery diagrams

We give an explicit formula to compute the rotation number of a nullhomologous Legendrian knot in contact (1/n)-surgery diagrams along Legendrian links and obtain a corresponding result for the self-linking number of transverse knots. Moreover, we extend the formula by Ding–Geiges–Stipsicz for computing the d₃-invariant to (1/n)-surgeries.     

On nonuniform dichotomy for stochastic skew-evolution semiflows in Hilbert spaces

In this paper we study a general concept of nonuniform exponential dichotomy in mean square for stochastic skew-evolution semiflows in Hilbert spaces. We obtain a variant for the stochastic case of some well-known results, of the deterministic case, due to R. Datko: Uniform asymptotic stability of evolutionary processes in a Banach space, SIAM J. Math. Anal., 3(1972), 428–445. Our approach is based on the extension of some techniques used in the deterministic case for the study of asymptotic behavior of skew-evolution semiflows in Banach spaces.     

Splitting of liftings in products of probability spaces II

For a probability measure R on a product of two probability spaces that is absolutely continuous with respect to the product measure we prove the existence of liftings subordinated to a regular conditional probability and the existence of a lifting for R with lifted sections which satisfies in addition a rectangle formula. These results improve essentially some of the results from the former work of the authors [W. Strauss, N.D. Macheras, K. Musia?, Splitting of liftings in products of probability spaces, Ann. Probab. 32 (2004) 2389-2408], by weakening considerably the assumptions and by presenting more direct and shorter proofs. In comparison with [W. Strauss, N.D. Macheras, K. Musia?, Splitting of liftings in products of probability spaces, Ann. Probab. 32 (2004) 2389-2408] it is crucial for applications intended that we can now prescribe one of the factor liftings completely freely. We demonstrate the latter by applications to τ-additive measures, transfer of strong liftings, and stochastic processes.     

Computation of the homology ofΩ(X∨Y)

Summary We compute the homology of Ω(X∨Y) (the loop space of the wedge of the spaces X and Y), in terms of the homogies of ΩX and ΩY. To do this we use the fact that our problem is equivalent to the computation of the homology of the free product of two topological groups in terms of the homologies of the topological groups. We establish a multiple Kunneth formula with coefficients over a Dedekind domain, which is used to prove a Kunneth like formula involves homologies over a Dedekind domain and generalizes similar results with integral or field coefficients. Over a principal ideal domain the formula for a free product is made more specific. Entrata in Redazione il 31 maggio 1978.     

Existence, uniqueness and stability of Cm solutions of iterative functional equations

In this paper we discuss a relatively general kind of iterative functional equation G(x,f(x),..., fn(x))=0 (for all x∈J), where J is a connected closed subset of the real number axis R, G∈Cm(Jn+1, R), and n≥2. Using the method of approximating fixed points by small shift of maps, choosing suitable metrics on functional spaces and finding a relation between uniqueness and stability of fixed points of maps of general spaces, we prove the existence, uniqueness and stability of Cm solutions of the above equation for any integer m≥0 under relatively weak conditions, and generalize related results in reference in different aspects.     

Local midpoints on smooth manifolds

In this paper we consider three methods for obtaining midpoints, primarily midpoints of geodesics of sprays, but also midpoints of symmetry (in symmetric spaces), and metric midpoints (in Riemannian manifolds). We derive general conditions under which these approaches yield the same result. We also derive a version of the Lie–Trotter formula based on the midpoint operation and use it to show that continuous maps preserving (local) midpoints are smooth.     

Ishikawa type iterative algorithm for completely generalized nonlinear quasi-variational-like inclusions in Banach spaces

In this paper, we consider completely generalized nonlinear quasi-variational-like inclusions in Banach spaces and propose an Ishikawa type iterative algorithm for computing their approximate solutions by applying the new notion of $J^{\eta }$-proximal mapping given in [R. Ahmad, A.H. Siddiqi, Z. Khan, Proximal point algorithm for generalized multi-valued nonlinear quasi-variational-like inclusions in Banach spaces, Appl. Math. Comput. 163 (2005) 295–308]. We prove that the approximate solutions obtained by the proposed algorithm converge to the exact solution of our quasi-variational-like inclusions. The results presented in this paper extend and improve the corresponding results of [R. Ahmad, A.H. Siddiqi, Z. Khan, Proximal point algorithm for generalized multi-valued nonlinear quasi-variational-like inclusions in Banach spaces, Appl. Math. Comput. 163 (2005) 295–308; X.P. Ding, F.Q. Xia, A new class of completely generalized quasi-variational inclusions in Banach spaces, J. Comput. Appl. Math. 147 (2002) 369–383; N.J. Huang, Generalized nonlinear variational inclusions with non-compact valued mappings, Appl. Math. Lett. 9(3) (1996) 25–29; A. Hassouni, A. Moudafi, A perturbed algorithm for variational inclusions, J. Math. Anal. Appl. 185(3) (1994) 706–712]. Some special cases are also discussed.     

Convergence of multi-level iterative aggregation-disaggregation methods

This paper introduces an error propagation formula of a certain class of multi-level iterative aggregation-disaggregation (IAD) methods for numerical solutions of stationary probability vectors of discrete finite Markov chains. The formula can be used to investigate convergence by computing the spectral radius of the error propagation matrix for specific Markov chains. Numerical experiments indicate that the same type of the formula could be used for a wider class of the multi-level IAD methods. Using the formula we show that for given data there is no relation between convergence of two-level and of multi-level IAD methods.     

Stochastic integration with respect to Gaussian processesIntégrale stochastique pour les processus gaussiens

We construct a Stratonovitch–Skorohod-like stochastic integral for general Gaussian processes. We study its sample path regularity and one of its numerical approximating schemes. We also analyze the way it is transformed by an absolutely continuous change of probability and we give an Itô formula. To cite this article: L. Decreusefond, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 903–908.     

General tridiagonal random matrix models, limiting distributions and fluctuations

In this paper we discuss general tridiagonal matrix models which are natural extensions of the ones given in Dumitriu and Edelman (J. Math. Phys. 43(11): 5830–5847, 2002; J. Math. Phys. 47(11):5830–5847, 2006). We prove here the convergence of the distribution of the eigenvalues and compute the limiting distributions in some particular cases. We also discuss the limit of fluctuations, which, in a general context, turn out to be Gaussian. For the case of several random matrices, we prove the convergence of the joint moments and the convergence of the fluctuations to a Gaussian family. The methods involved are based on an elementary result on sequences of real numbers and a judicious counting of levels of paths.     

Petits espaces de Lebesgue et quelques applicationsOn small Lebesgue spaces and their applications

We prove some new properties of the small Lebesgue spaces introduced by Fiorenza [7]. Combining these properties with the Poincaré–Sobolev inequalities for the relative rearrangement (see [11]), we derive some new and precises estimates either for small Lebesgue–Sobolev spaces or for quasilinear equations with data in the small Lebesgue spaces. To cite this article: A. Fiorenza, J.-M. Rakotoson, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 23–26     

Methods for Evaluating Density Functions of Exponential Functionals Represented as Integrals of Geometric Brownian Motion

The purpose of this paper is to present a survey on Yor's formula on the probability densities of the exponential functionals represented as integrals in time of geometric Brownian motions and to present results on numerical computations for the densities. We perform the computations via another formula for the densities obtained by Dufresne and we show numerically the desired coincidence in some cases. As an application, we compute the price of an Asian option. AMS 2000 Subject Classification: 65C50, 60J65     

Existence and asymptotic behaviour of solutions to first- and second-order difference equations with periodic forcing

By using previous results of Djafari Rouhani for non-expansive sequences in Refs (Djafari Rouhani, Ergodic theorems for nonexpansive sequences in Hilbert spaces and related problems, Ph.D. Thesis, Yale University, Part I (1981), pp. 1–76; Djafari Rouhani, J. Math. Anal. Appl. 147 (1990), pp. 465–476; Djafari Rouhani, J. Math. Anal. Appl. 151 (1990), pp. 226–235), we study the existence and asymptotic behaviour of solutions to first-order as well as second-order difference equations of monotone type with periodic forcing. In the first-order case, our result extends to general maximal monotone operators, the discrete analogue of a result of Baillon and Haraux (Rat. Mech. Anal. 67 (1977), 101–109) proved for subdifferential operators. In the second-order case, our results extend among other things, previous results of Apreutesei (J. Math. Anal. Appl. 288 (2003), 833–851) to the non-homogeneous case, and show the asymptotic convergence of every bounded solution to a periodic solution.