Processing fuzzy set membership functionals as vectors

A framework is presented for processing fuzzy sets for which the universe of discourse X = {x} is a separable Hilbert Space, which, in particular, may be a Euclidian Space. In a given application, X would constitute a feature space. The membership functions of sets in such X are then “membership functionals”, that is, mappings from a vector space to the real line. This paper considers the class Φ of fuzzy sets A, the membership functionals μ _A of which belong to a Reproducing Kernel Hilbert Space (RKHS) F(X) of bounded analytic functionals on X, and satisfy the constraint . These functionals can be expanded in abstract power series in x, commonly known as Volterra functional series in x. Because of the one-to-one relationship between the fuzzy sets A and their respective μ _A , one can process the sets A as objects using their μ _A as intermediaries. Thus the structure of the uncertainty present in the fuzzy sets can be processed in a vector space without descending to the level of processing of vectors in the feature space as usually done in the literature in the field. Also, the framework allows one to integrate human and machine judgments in the definition of fuzzy sets; and to use concepts analogous to probabilistic concepts in assigning membership values to combinations of fuzzy sets. Some analytical and interpretive consequences of this approach are presented and discussed. A result of particular interest is the best approximation of a membership functional μ _A in F(X) based on interpolation on a training set {(v ⁱ , u ⁱ ),i = 1, . . . , q} and under the positivity constraint. The optimal analytical solution comes out in the form of an Optimal Interpolative Neural Network (OINN) proposed by the author in 1990 for best approximation of pattern classification systems in a F(X) space setting. An example is briefly described of an application of this approach to the diagnosis of Alzheimer’s disease.     

Accurate evaluation of divided differences for polynomial interpolation of exponential propagators

In this paper, we propose an approach to the computation of more accurate divided differences for the interpolation in the Newton form of the matrix exponential propagator φ(hA)v, φ (z) = (e ^z − 1)/z. In this way, it is possible to approximate φ (hA)v with larger time step size h than with traditionally computed divided differences, as confirmed by numerical examples. The technique can be also extended to “higher” order φ _k functions, k≥0.     

Energy Evolution in Time-Dependent Harmonic Oscillator

The theory of adiabatic invariants has a long history, and very important implications and applications in many different branches of physics, classically and quantally, but is rarely founded on rigorous results. Here we treat the general time-dependent one-dimensional harmonic oscillator, whose Newton equation q + ω²(t)q = 0 cannot be solved in general. We follow the time-evolution of an initial ensemble of phase points with sharply defined energy E_o at time t = 0 and calculate rigorously the distribution of energy E₁ after time t = T, which is fully (all moments, including the variance μ²) determined by the first moment Ē₁. For example, μ² = E²_o[(Ē₁/E_o)² — (ω(T)/ω(0))²]/2, and all higher even moments are powers of μ², whilst the odd ones vanish identically. This distribution function does not depend on any further details of the function ω(t) and is in this sense universal. In ideal adiabaticity Ē₁ = ω(T)E_o/ω(0), and the variance μ,² is zero, whilst for finite T we calculate Ē₁, and μ² for the general case using exact WKB-theory to all orders. We prove that if ω(t)is of class ^m (all derivatives up to and including the order m are continuous) μ, ∝ T^{−(m + 1)}) whilst for the class °° it is known to be exponential μ ∝ exp(—aT).     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

Outer Interval Solution of the Eigenvalue Problem under General Form Parametric Dependencies

The paper addresses the problem of determining an outer interval solution of the parametric eigenvalue problem A(p)x = λx, A(p) ∈ ℝ^n×n for the general case where the matrix elements a_ij(p) are continuous nonlinear functions of the parameter vector p, p belonging to the interval vector p. A method for computing an interval enclosure of each eigenpair (λ_μ, x^(μ)), μ = 1, ..., n, is suggested for the case where λ_μ is a simple eigenvalue. It is based on the use of an affine interval approximation of a_ij(p) in p and reduces, essentially, to setting up and solving a real system of n or 2n incomplete quadratic equations for each real or complex eigenvalue, respectively.     

On the bottom summation

We consider summation of consecutive values (φ(v), φ(v + 1), ..., φ(w) of a meromorphic function φ(z), where v, w ∈ ℤ. We assume that φ(z) satisfies a linear difference equation L(y) = 0 with polynomial coefficients, and that a summing operator for L exists (such an operator can be found—if it exists—by the Accurate Summation algorithm, or, alternatively, by Gosper’s algorithm when ordL = 1). The notion of bottom summation which covers the case where φ(z) has poles in ℤ is introduced. The text was submitted by the authors in English.     

From liveness to promptness

Liveness temporal properties state that something “good” eventually happens, e.g., every request is eventually granted. In Linear Temporal Logic (LTL), there is no a priori bound on the “wait time” for an eventuality to be fulfilled. That is, F θ asserts that θ holds eventually, but there is no bound on the time when θ will hold. This is troubling, as designers tend to interpret an eventuality F θ as an abstraction of a bounded eventuality F ^≤k θ, for an unknown k, and satisfaction of a liveness property is often not acceptable unless we can bound its wait time. We introduce here prompt-LTL, an extension of LTL with the prompt-eventually operator F _p . A system S satisfies a prompt-LTL formula φ if there is some bound k on the wait time for all prompt-eventually subformulas of φ in all computations of S. We study various problems related to prompt-LTL, including realizability, model checking, and assume-guarantee model checking, and show that they can be solved by techniques that are quite close to the standard techniques for LTL.     

Complexities of Homomorphism and Isomorphism for Definite Logic Programs

A homomorphism (?) of logic programs from P to P' is a function mapping Atoms(P) to Atoms(P') and it preserves complements and program clauses. For each definite program clause a←a1,...,an∈P it implies that (?)(a)←(?)(a1),...,(?)(an) is a program clause of P'. A homomorphism (?) is an isomorphism if (?) is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem (HOM-LP) for definite logic programs is NP-complete, and the isomorphism problem (ISO-LP) is equivalent to the graph isomorphism problem (GI).     

Visual space geometry derived from occlusion axioms

In our previous work [1] occlusion phenomena were considered as a foundation for development of geometrical structures in the visual field. The laws of occlusion were adapted to form the basis of an axiomatic system. Occlusion is formalized as a ternary relation and its properties include symmetry and transistivity. This leads to the definition of an abstract visual space (AVS). The geometry of an AVS is the subject of this research. Typical examples of an AVS are the convex open subsets of an n-dimensional real affine space for n2 or more generally, the convex open subsets of any n-dimensional affine space over some totally ordered field F, commutative or noncommutative. In an AVS we define such geometrical objects as lines, planes, convex bodies, closed and open subsets, etc. For any n-dimensional (n3) AVS X we construct an n-dimensional projective space P _F ⁿ over a totally ordered commutative or noncommutative field F and produce an embedding i: X xP _F ⁿ such that the image i(X) is open in P _F ⁿ and every line l in X is of the form l=i ^-1 (Li(X)) for some line L in P _F ⁿ. The mapping i and the field F depend on X and are unique up to isomorphism. We obtain a characterization of X via this embedding which is complete in the case of archimedean fields F. If F=R, the field of real numbers, i induces an embedding j: X ¶ A _R ⁿ and j(X) is a convex open subset of an affine space A _R ⁿ. If FR there can exist other types of AVS.     

Automatic Computation of a Linear Interval Enclosure

Recently, an alternative interval approximation F(X) for enclosing a factorable function f(x) in a given box X has been suggested. The enclosure is in the form of an affine interval function F(X)= a _i X _i +B where only the additive term B is an interval, the coefficients a _i being real numbers. The approximation is applicable to continuously differentiable, continuous and even discontinuous functions.In this paper, a new algorithm for determining the coefficients a _i and the interval B of F(X) is proposed. It is based on the introduction of a specific generalized representation of intervals which permits the computation of the enclosure considered to be fully automated.     

Wavelet solution of variable order pseudodifferential equations

Sobolev spaces H ^m(x)(I) of variable order 0<m(x)<1 on an interval I⊂ℝ arise as domains of Dirichlet forms for certain quadratic, pure jump Feller processes X _t ∈ℝ with unbounded, state-dependent intensity of small jumps. For spline wavelets with complementary boundary conditions, we establish multilevel norm equivalences in H ^m(x)(I) and prove preconditioning and wavelet matrix compression results for the variable order pseudodifferential generators A of X.     

On horizons and wormholes in k-essence theories

We study the properties of possible static, spherically symmetric configurations in k-essence theories with the Lagrangian functions of the form F(X), X ≡ ?,_α ?,^α. A no-go theorem has been proved, claiming that a possible black-hole-like Killing horizon of finite radius cannot exist if the function F(X) is required to have a finite derivative dF/dX. Two exact solutions are obtained for special cases of kessence: one for F(X) = F ₀ X ^1/3, another for F(X) = F ₀|X|^1/2 ? 2Λ, where F ₀ and Λ are constants. Both solutions contain horizons, are not asymptotically flat, and provide illustrations for the obtained nogo theorem. The first solution may be interpreted as describing a black hole in an asymptotically singular space-time, while in the second solution two horizons of infinite area are connected by a wormhole.     

Communication Complexity Under Product and Nonproduct Distributions

We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let R_∈(f) and $D^\mu_\in (f)$D^\mu_\in (f) denote the randomized and μ-distributional communication complexities of f, respectively (∈ a small constant). Yao’s well-known minimax principle states that $R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}$R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximum is taken over product distributions only, rather than all distributions μ. We give a strong negative answer to this question. Specifically, we prove the existence of a function f : {0, 1}ⁿ ×{0, 1}ⁿ ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which max_{μ product} {D^m _? (f)} = Q(1)  but R _? (f) = Q(n)\{D^\mu_\in (f)\} = \Theta(1) \,{\textrm but}\, R_{\in} (f) = \Theta(n). We also obtain an exponential separation between the statistical query dimension and signrank, solving a problem previously posed by the author (2007).     

On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.     

Deep lithography with a low energy synchrotron source: fabrication of X-ray refractive single lenses

 Lithography as deep as 400 μm has been carried out to fabricate X-rays refractive lenses using a low energy synchrotron source (AURORA-2 S, 0.7 GeV). The lens made of PMMA has two parabolic curvatures with radii R=4 μm and apertures A=2(2Rz)^1/2=179 μm, thus the aspect ratio z/R=250 for its curvatures, which is too great for traditional techniques to achieve. Upon fabrication of the lenses, precision of the curvatures has been evaluated by digital imaging analysis. The lens can singly focus a beam of hard X-rays into several microns at a reasonable focal length F=1.5 m. Advantages of using a low energy source for the LIGA process will be discussed regarding problems such as thick absorbers demanded by the LIGA mask and heat-load occurring in thick resist layers. Received: 10 August 2001/Accepted: 24 September 2001     

Probability densities for conditional statistics in the cubic sensor problem

This paper applies the techniques of Malliavin’s stochastic calculus of variations to Zakai’s equation for the one-dimensional cubic sensor problem in order to study the existence of densities of conditional statistics. Let {X _t} be a Brownian motion observed by a cubic sensor corrupted by white noise, and let denote the unnormalized conditional estimate of φ(X _i ). If φ₁,...,φ _n are linearly independent, and if , it is shown that the probability distribution of admits a density with respect to Lebesgue measure for anyn. This implies that, at any fixed time, the unnormalized conditional density cannot be characterized by a finite set of sufficient statistics. Research supported in part by NSF Grant No. MCS-8301880 and by the Institute for Mathematics and It Applications, Minneapolis, Minnesota.     

Effects of actuating waveform,ink property,and nozzle size on piezoelectrically driven inkjet droplets

Computational fluid dynamics and micro-flow visualization (μ-FV) have been complementarily performed to study the evolution of a single droplet ejected from a bend-mode piezoelectric inkjet printhead. The numerical simulation is characterized by the coupled piezoelectric-structural-fluid solution procedure and verified by the μ-FV results. The in-house numerical code is subsequently applied to investigate the influences of electric voltage φ _pp, pulse shape, ink property, and nozzle diameter D _n on the droplet volume, velocity, and configurations. φ _pp studied ranges from 14 to 26 V and pulse shape is explored by varying the key time intervals with fixed voltage slopes. The influence of ink property is examined by investigating the dynamic viscosity μ and surface tension σ separately. Investigation on the effects of nozzle diameter is also conducted by decreasing D _n from 26 to 11 at 3 μm interval. The computed results are found in good agreement with the experimental ones. New findings are to discover the critical ranges of electric waveform parameters, μ, and σ outside which the phenomena of satellite droplets and puddle formation at the nozzle opening are absent. In addition, the imbedded physical rationales for these critical ranges are provided. The results are also new in terms of the identifications of the critical σ and D _n for the reference of improving the droplet quality.     

Transparent partial order reduction

Partial Order Reduction (POR) techniques improve the basic model checking algorithm by reducing the numbers of states and transitions explored in verifying a property of the model. In the “ample set” POR framework for the verification of an LTL_−X formula φ, one associates to each state s a subset T _s of the set of all transitions enabled at s. The approach requires that whenever T _s is a proper subset, the transitions in T _s must be invisible, i.e., their execution can never change the truth values of the atomic propositions occurring in φ. In this paper, we show that the invisibility restriction can be relaxed: for propositions that only occur negatively in φ, it suffices that the transitions in T _s merely never change the truth value from true to false, and for those that occur only positively, from false to true. This opens up opportunities for reduction, in many commonly occurring scenarios, that would not be allowed by the stricter invisibility criterion.     

On estimation of the probability of absence of collisions of some random mappings

Let X and Y be finite sets and φ: (X,Y) →Y be a mapping. Consider a random mapping i → φ(x_i,y_i), where x_i are arbitrarily chosen from the set X, whereas (y_i) is a random sample from Y without replacement. A two-sided bound is derived for the probability of absence of collisions of this mapping. A case of mapping, defined as φ(x, y)=x+ y modulo n, is considered in particular. The results may be used in the selection of identification codes. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 132–137, January–February, 2000.     

On Nonnegative matrices generating a finite multiplicative monoid

Square nonnegative matrices with the property that the multiplicative monoid M(A) generated by the matrix A is finite are characterized in several ways. At first, the least general upper bound for the cardinality of M(A) is derived. Then it is shown that any square nonnegative matrix is cogredient to a lower triangular block form with the diagonal consisting of three blocks L, A ₀, and M where L and M are strictly lower triangular, A ₀ has no zero rows or columns, and M(A) is finite if and only if. M(A ₀) is so. Several criteria for, M(A ₀) to be finite are presented. One of the normal forms of A applies very well to the characterization of the nonnegative solutions of each of the matrix equations X ^k = 0, X ^k = 1, X ^k = X, and X ^k = X ^T where k > 1 is an integer. It also leads to a polynomial time algorithm for deciding whether or not M(A) is finite, if the entries of A are nonnegative rationals.