Exact learning of DNF formulas using DNF hypotheses

We show the following: (a) For any ε>0, log^(3+ε)n-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) For sufficiently large t, t-term DNF formulas cannot be polynomial-query learned with membership and equivalence queries that use t^1+ε-term DNF formulas as hypotheses, for some ε<1 (c) Read-thrice DNF formulas are not polynomial-query learnable with membership and proper equivalence queries. (d) logn-term DNF formulas can be polynomial-query learned with membership and proper equivalence queries. (This complements a result of Bshouty, Goldman, Hancock, and Matar that -term DNF can be so learned in polynomial time.)Versions of (a)-(c) were known previously, but the previous versions applied to polynomial-time learning and used complexity theoretic assumptions. In contrast, (a)-(c) apply to polynomial-query learning, imply the results for polynomial-time learning, and do not use any complexity-theoretic assumptions.     

Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

Compact Numerical Quadrature Formulas for Hypersingular Integrals and Integral Equations

In the first part of this work, we derive compact numerical quadrature formulas for finite-range integrals $I[f]=\int^{b}_{a}f(x)\,dx$ , where f(x)=g(x)|x?t| ^?? , ?? being real. Depending on the value of ??, these integrals are defined either in the regular sense or in the sense of Hadamard finite part. Assuming that g??C ^??[a,b], or g??C ^??(a,b) but can have arbitrary algebraic singularities at x=a and/or x=b, and letting h=(b?a)/n, n an integer, we derive asymptotic expansions for ${T}^{*}_{n}[f]=h\sum_{1\leq j\leq n-1,\ x_{j}\neq t}f(x_{j})$ , where x _j =a+jh and t??{x ₁,??,x _n?1}. These asymptotic expansions are based on some recent generalizations of the Euler?CMaclaurin expansion due to the author (A.?Sidi, Euler?CMaclaurin expansions for integrals with arbitrary algebraic endpoint singularities, in Math. Comput., 2012), and are used to construct our quadrature formulas, whose accuracies are then increased at will by applying to them the Richardson extrapolation process. We pay particular attention to the case in which ??=?2 and f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ , which arises in the context of periodic hypersingular integral equations. For this case, we propose the remarkably simple and compact quadrature formula $\widehat{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)-\pi^{2} g(t)h^{-1}$ , and show that $\widehat{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, and that it is exact for a class of singular integrals involving trigonometric polynomials of degree at most n. We show how $\widehat{Q}_{n}[f]$ can be used for solving hypersingular integral equations in an efficient manner. In the second part of this work, we derive the Euler?CMaclaurin expansion for integrals $I[f]=\int^{b}_{a} f(x)dx$ , where f(x)=g(x)(x?t) ^?? , with g(x) as before and ??=?1,?3,?5,??, from which suitable quadrature formulas can be obtained. We revisit the case of ??=?1, for which the known quadrature formula $\widetilde{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)$ satisfies $\widetilde{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, when f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ . We show that this formula too is exact for a class of singular integrals involving trigonometric polynomials of degree at most n?1. We provide numerical examples involving periodic integrands that confirm the theoretical results.     

Some remarks on a conjecture in parameter adaptive control

A.S. Morse has raised the following question: Do there exist differentiable functions

$\text{f:R}{}^2\text{→ R}\text{and}\text{g:R}{}^2\text{→ R}$

with the property that for every nonzero real number λ and every (x₀, y₀) ∈ $\text{R}$² the solution (x(t),y(t)) of

$\text{x}\text{?}\text{(t) = x(t) + λf(x(t),y(t))}$

,

$\text{y}\text{?}\text{(t) = g(x(t),y(t))}$

,

$\text{x(0) = x}{}_0\text{, y(0) = y}{}_0$

, is defined for all t ? 0 and satisfies

$\text{lim}\text{t → + ∞}$

and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no.     

Optimal scheduling of contract algorithms with soft deadlines

A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time \(w(t)\le c \cdot t\), for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.     

Temporal logics in AI: Semantical and ontological considerations

One way to represent temporal information in a logical formalism is by associating “proposition types” with time points or time intervals. The way this is usually done in AI is by “reifying” propositions, so that what otherwise would have been formulas actually appear as arguments to some “predicate,” say TRUE, as in TRUE(t₁, t₂, COLOR(HOUSE, RED)). This way time is referred to explicitly, while retaining its special notational and conceptual status.We examine this method by looking closely at two of the more influential formalisms featuring reified propositions, those of Allen and McDermott. We show that these do not have completely clear semantics, and that they make some unfortunate and unnecessary ontological commitments. Finally, we present a new formalism and demonstrate that it does not suffer from these disadvantages.     

Conservative difference schemes for diffusion problems with boundary and interface conditions

For 0≤x≤1, 0≤t≤T we consider the diffusion equation $$\gamma (x)u_t (x, t) - (B u)_x (x, t) = f(x, t)$$ with (alternatively)B u:=(a(x)u) _x +b(x)u ora(x)u _x +β(x)u. There are given initial valuesu(x,0), influx rates?(B u) (0,t) and (B u) (1,t) across the lateral boundaries and an influx rate (B u) (ζ?0,t)?(B u) (ζ+0,t) at an interface ζ∈(0, 1) where the elsewhere smooth functions γ,a, b, β are allowed to have jump discontinuities.a and γ are assumed to be positive. Interpretingu(x, t) as temperature and γ(x) u (x, t) as energy density we can easily express the total energy \(E(t) = \int\limits_0^1 {\gamma (x) u (x, t)} \) in terms of integrals of the given data. We describe and analyse explicit and implicit one-step difference schemes which possess a discrete quadrature analogue exactly matchingE(t) at the time grid points. These schemes also imitate the isotonic dependence of the solution on the data. Hence stability can be proved by Gerschgorin's method and, under appropriate smoothness assumptions, convergence is 0 ((Δx)²+Δt).     

Recovering the initial state of an infinite-dimensional system using observers

Let A be the generator of a strongly continuous semigroup T on the Hilbert space X, and let C be a linear operator from D(A) to another Hilbert space Y (possibly unbounded with respect to X, not necessarily admissible). We consider the problem of estimating the initial state z₀∈D(A) (with respect to the norm of X) from the output function y(t)=CT_tz₀, given for all t in a bounded interval [0,τ]. We introduce the concepts of estimatability and backward estimatability for (A,C) (in a more general way than currently available in the literature), we introduce forward and backward observers, and we provide an iterative algorithm for estimating z₀ from y. This algorithm generalizes various algorithms proposed recently for specific classes of systems and it is an attractive alternative to methods based on inverting the Gramian. Our results lead also to a very general formulation of Russell’s principle, i.e., estimatability and backward estimatability imply exact observability. This general formulation of the principle does not require T to be invertible. We illustrate our estimation algorithms on systems described by wave and Schrödinger equations, and we provide results from numerical simulations.     

Alcune formule per il calcolo numerico della transformata di Fourier

In this paper we get three formulas to compute Fourier integral. The formulas are essentially a linear combination of values of the functionf(t) with weight coefficients, which are independent of thef(t) and of the parameter ω. The formulas are obtained by means of a polinomial approximation off(t) on each interval (kmτ, (k+1)mτ) wherem is an integer and τ is the period of the trigonometric function.      

Time-space trade-offs for compressed suffix arrays

Given a binary string of length n, we give a representation of its suffix array that takes O(nt(lgn)^1/t) bits of space such that given i,1?i?n, the ith entry in the suffix array of the string can be retrieved in O(t) time, for any parameter 1?t?lglgn. For t=lglgn, this gives a compressed suffix array representation of Grossi and Vitter [Proc. Symp. on Theory Comput., 2000, pp. 397-406]. For t=O(1/ε), this gives the best known (in terms of space) compressed suffix array representation with constant query time. From this representation one can construct a suffix tree structure for a text of length n, that uses o(nlgn) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/lgn+k) time. No such structure was known earlier.     

A general treatment of rearrangement problems in a linear storage

Different cost models of allocation and rearrangement of a set {F₁,F₂…F_n} of files are investigated in the paper. It is assumed that the distribution p₁(t) of the reference string ξ(t) depends on the user's activity. For large values of n a limiting process is used and a continuous rearrangement model is introduced, in which the integral formulas can be handled simpler than those summation formulas in the discrete case. Some open problems could be solved by the help of this treatment. The connection with order statistical treatment is found and used for a simple user activity model. The formulas can be used to approximate the average head movement, in case of different distributions, in optimal deterministic file allocation problems. Deterministic and stochastic strategies of allocation and rearrangement are studied and compared.     

Uniqueness Results for Image Reconstruction from Features on Curves in α-Scale Spaces

A sufficient condition is presented for two-dimensional images on a finite rectangular domain Ω=(?A,A)×(?B,B) to be completely determined by features on curves t?(ξ(t),t) in the three-dimensional domain Ω×(0,∞) of an α-scale space. For any fixed finite set of points in the image, the values of the α-scale space at these points at all scales together do not provide sufficient information to reconstruct the image, even if spatial derivatives up to any order are included as well. On the other hand, the image is completely fixed by the values of the scale space and its derivative along any straight line in Ω×(0,∞) for which ξ:(0,∞)→Ω is linear but not constant. A similar result holds for curves for which ξ is of the form ξ(t)=(ξ ₁(t),0) with ξ ₁ periodic and not constant. If the locations at which the scale space is evaluated form a curve on a cylinder in Ω×(0,∞) with some periodic structure, like a helix, then it is sufficient to evaluate the α-scale space without spatial derivatives.     

Predicting the future of functions on flows

Let Ω be a topological space,S _t ∈ R (R the reals) a homeomorphism group on Ω andμ a Borel measure invariant with respect toS _t , (μ(Ω)=1); forP ∈Ω putS _t (P)=P _t . Assumef ∈L ₂(Ω,μ); according to E. Hopf there is for almost everyP ∈ Ω a well-determined spectral function σ(P,λ),λ ∈ R with lim \(T^{ - 1} \int_0^T {f(P_{t + s} )\overline {f(P_t )} dt = \int_{ - \infty }^{ + \infty } {e^{i\lambda s} d\sigma (P\lambda )} }\) . The question to be considered is:^*) if for a fixedP ∈ Ω we know the “past”f(P _t ), t ≦ 0, is it then possible to compute (or “predict”) the future valuesf(P _t ), t > 0? By using ideas from linear prediction theory we show that if \(\int_{ - \infty }^{ + \infty } {(1 + \lambda ^2 )\log \frac{d}{{d\lambda }}\sigma (P,\lambda )} d\lambda = - \infty\) then the prediction required by^*) is possible. An algorithm is described which accomplishes the prediction.     

三值乘积逻辑系统Π3中的随机化研究

利用赋值集的随机化方法,在三值乘积逻辑∏₃提出了公式的随机真度,证明了所有公式的随机真度之集在[0,1]中没有孤立点;给出了两公式间的D_∏3-相似度与伪距离的概念,并建立了D_∏3-逻辑度量空间,证明了此空间没有孤立点。     

A probabilistic analysis of an error-correcting algorithm for the towers of Hanoi puzzle

Let S be a set of n horizontal and vertical segments on the plane, and let s, t ∈ S. A Manhattan path (of length k) from s to t is an alternating sequence of horizontal and vertical segments, s = r₀, r₁,…,r_k = t, such that r_i intersects r_i+1, 0 ? i < k. An O(n log n) time O(n log n) space algorithm is presented which, given S and t, finds a tree of shortest Manhattan paths from all s ∈ S to t. The algorithm relies on a new data structure which makes it possible to find in O(log n + p) time all p segments currently in S which intersect a given s ∈ S, and which support a deletion of any segment from S in O(log n) time, where we assume that the cost of these operations is accumulated over the whole algorithm. The structure makes use of the recently discovered Gabow and Tarjan's linear time version of the union-find algorithm on consecutive sets. We prove an Ω(n log n) lower bound on the complexity of deciding whether there is a Manhattan path between two given segments, under the linear decision tree model. Finally, some applications of the Manhattan path algorithm are indicated.     

Lukasiewicz三值逻辑系统中的随机化研究

利用赋值集的随机化方法,在三值逻辑L3中提出了公式的随机真度,证明了所有公式的随机真度之集在[0,1]中没有孤立点;给出了两公式间的DL3-相似度与伪距离的概念,并建立了DL3-逻辑度量空间,证明了此空间没有孤立点。     

Numerical evaluation of a solution of a special mixed-type differential-difference equation

The function * $$f(t) = \frac{{e^{ - \alpha \gamma } }}{\pi }\int\limits_0^\infty {\cos t \xi e^{\alpha Ci(\xi )} \frac{{d\xi }}{{\xi ^\alpha }},t \in R,\alpha > 0} $$ [Ci(x)=cosine integral, γ=Euler's constant] is studied and numerically evaluated;f is a solution to the following mixed type differential-difference equation arising in applied probability: ** $$tf'(t) = (\alpha - 1)f(t) - \frac{\alpha }{2}[f(t - 1) + f(t + 1)]$$ satisfying the conditions: i) $$f(t) \geqslant 0,t \in R$$ , ii) $$f(t) = f( - t),t \in R$$ , iii) $$\int\limits_{ - \infty }^{ + \infty } {f(\xi )d\xi = 1} $$ . Besides the direct numerical evaluation of (*) and the derivation of the asymptotic behaviour off(t) fort→0 andt→∞, two different iterative procedures for the solution of (**) under the conditions (i) to (iii) are considered and their results are compared with the corresponding values in (*). Finally a Monte Carlo method to evaluatef(t) is considered.     

A method for the calculation of eigenfunction expansions

In this paper, a method is presented for the calculation of the coefficients of the series expansion of a function f(t), in the base orthonormal set made up by the eigenfunctions of the self-adjoint operator $\text{L: L(x(t)) = (}\text{d}\text{dt}\text{)( p(t)(}\text{dx(t)}\text{dt}\text{))?q(t)x(t)}$. We show that the values of the numbers $\text{t}\text{}$x_k> can be obtained by solving the differential equation L + λ) y(t) = Kf(t), in the interval of definition, for each of the eigenvalues λ of L and by using as initial conditions those which determine one of its associated orthonormal functions. This makes the method specially interesting for its implementation on a hybrid computer: One advantage of the proposed method is that the analysis of f(t) does not require the simultaneous presence of the functions of the base set and the problem signal, thus eliminating both the problems of the synchronized generation of signals and the need for storing it in memory.     

Uniqueness for ordinary differential equations

Various criteria are known for assuring uniqueness of the solution of a system ofn ordinary differential equations,x = f(t, x), with initial conditionx(t ₀) = x₀. Most of these involve some sort of relaxed Lipschitz condition onf(t, x), with respect tox, valid on an open setD R ¹⁺ⁿ which contains the point (t ₀, x₀). The present paper generalizes (and unifies) a number of known uniqueness criteria to cover cases when (t ₀, x₀) lies on the boundary ofD. Research partially supported by NSF Grant GP-37838.