Mann and Ishikawa iterations with errors for non-lipschitzian mappings in Banach spaces

Let C be a nonempty closed convex subset of a uniformly convex Banach space and let T : C → C be completely continuous asymptotically nonexpansive in the intermediate sense. In this paper, we prove that the Ishikawa (and Mann) iteration process with errors converges strongly to some fixed point of T, which generalizes the recent results due to Huang [1].     

Discontinuous quasivariational-like inequalities

In this note, we deal with the following problem: given X Rⁿ, a multification gG : X → 2^X, two (single-valued) maps f : X → Rⁿ, η : X × X → Rⁿ, find a point x* X such that x* Γ (x*) and f(x*), η(x,x*) ≥ 0 for all x Γ(x*). We prove an existence theorem in which, in particular, the function f is not supposed to be continuous.     

On some dynamical subsets of the rauzy fractal

Let ( ,(+1)_n) be the adic system associated to the substitution: 1 → 12,…,(n − 1) → 1n, n → 1. In Sirvent (1996) it was shown that there exist a subset Cⁿ of and a map h_n: C → Cⁿ such that the dynamical system (C, h_n) is semiconjugate to ( ). In this paper we compute the Hausdorff and Billingsley dimensions of the geometrical realizations of the set Cⁿ on the (n− l)-dimensional torus. We also show that the dynamical system (Cⁿ,h_n) cannot be realized on the (n − 1)-torus.     

On renaming a set of clauses as a Horn set

Let S = {C₁, …, C_m} be a set of clauses in the propositional calculus and let n denote the number of variables appearing these clauses. We present and O(mn) time algorithm to test whether S can be renamed as a Horn set.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

Séparateurs dans les mots infinis engendrés par morphismes

Let x be an infinite word on a finite alphabet A. For each position n, the separator of x at n is the smallest factor of x which begins at index n and that does not appear before in x. Let S_x be the function such that S_x(n) is the length of the separator of x at index n if it exists and otherwise 0.

We consider the problem of computing S_x in the case where x is generated by iterating a morphism σ : A* → A*. We prove the following theorem:     

Automatic rotational symmetry determination for shape analysis

The determination of the rotational symmetry of a shape is useful for object recognition and shape analysis in computer vision applications. In this paper, a simple, but effective, algorithm to analyse the rotational symmetry of a given closed-curve shape S is proposed. A circle C with the centroid of S as the circle center and the average radius of S as the circle radius is superimposed on S, resulting in the intersection of C and S at a set of points. By theoretical analysis, the relationship between the order N_s of the rotational symmetry of S and the number of intersection points between C and S is established. All the possible values for N_s are determined. And finally N_s is determined by evaluating the similarity between S and its rotated versions. In the proposed algorithm, only simple pixel operations and second-order moment function computation are involved. Several problems caused by the use of discrete image coordinates are analysed and solved for correct decision-making in the algorithm. Good experimental results are also included.     

On the number of occurrences of all short factors in almost all words

We previously proved that almost all words of length n over a finite alphabet A with m letters contain as factors all words of length k(n) over A as n→∞, provided limsup_n→∞ k(n)/log n<1/log m.

In this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where lim_n→∞ log s(n)/log n=0. In particular, this number of occurrences is bounded below by C log n as n→∞, for any absolute constant C>0.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.     

Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets B_r(v)∩C, vV (respectively, vVC), are all nonempty and different, where B_r(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.     

Combined super-/substring and super-/subsequence problems

Super-/substring problems and super-/subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. Here we investigate the complexity of a new type of such problem that forms a combination of a super-/substring and a super-/subsequence problem. Moreover we introduce different types of minimal superstring and maximal substring problems. In particular, we consider the following problems: given a set L of strings and a string S, (i) find a minimal superstring (or maximal substring) of L that is also a supersequence (or a subsequence) of S, (ii) find a minimal supersequence (or maximal subsequence) of L that is also a superstring (or a substring) of S. In addition some non-super-/non-substring and non-super-/non-subsequence variants are studied. We obtain several NP-hardness or even MAX SNP-hardness results and also identify types of “weak minimal” superstrings and “weak maximal” substrings for which (i) is polynomial-time solvable.     

Liquidus calculations for III-N semiconductors

Liquidus curves for III-N semiconducting compounds (AlN, GaN, and InN) are calculated. A quasi-chemical equilibrium approach also known as the first approximation in regular solution theory is used to calculate the T-X data. These calculations are based primarily on the heat and entropy of formation and the heat and entropy of fusion. A semi-empirical method is used to estimate the entropy and temperature of fusion values of the nitrides. The entropy of fusion of AlN is estimated to be 15.2 eu/mole with a melting point of 2800°C; for GaN, ΔS^F = 16.1 eu/mole with T_m = 1700°C; and for InN, ΔS^F = 14.5 eu/mole with T_m = 1200°C. These liquidus calculations are used to compute pressure of N₂ over both the column III rich and nitrogen rich regions of the nitrides. Implications for crystal growth are discussed.     

On computing the entropy of cellular automata

We study the topological entropy of a particular class of dynamical systems: cellular automata. The topological entropy of a dynamical system (X,F) is a measure of the complexity of the dynamics of F over the space X. The problem of computing (or even approximating) the topological entropy of a given cellular automata is algorithmically undecidable (Ergodic Theory Dynamical Systems 12 (1992) 255). In this paper, we show how to compute the entropy of two important classes of cellular automata namely, linear and positively expansive cellular automata. In particular, we prove a closed formula for the topological entropy of D-dimensional (D1) linear cellular automata over the ring Z_m (m2) and we provide an algorithm for computing the topological entropy of positively expansive cellular automata.     

Some results of fuzzy BCK-filters

Let X be a bounded BCK-algebra and f a fuzzy set in X. If a fuzzy BCK-filter μ in X satisfies that (i) fμ, (ii) for any fuzzy BCK-filter ν in X, fν implies μν, then μ is said to be generated by f and denote μ by [f) for short. In the present paper, we give a procedure to construct the [f) by f. As applications of this result we prove that the set of all fuzzy BCK-filters in a bounded BCK-algebra forms a complete and infinitely distributive lattice.     

Existence and uniqueness of unmixed solutions of the discrete-time algebraic Riccati equation

A solution X of a discrete-time algebraic Riccati equation is called unmixed if the corresponding closed-loop matrix Φ(X) has the property that the common roots of det(sI−Φ(X)) and det(I−sΦ(X)^*) (if any) are on the unit circle. A necessary and sufficient condition is given for existence and uniqueness of an unmixed solution such that the eigenvalues of Φ(X) lie in a prescribed subset of .     

Computerized formal solutions of dynamical systems with two degrees of freedom and an application to the Contopoulos potential—II : The near-resonance case

The article describes the periodic solutions of the Contopoulos system for the case of near-resonant frequencies (ω₂² = 1 and ω = 1 − ε²² The Lindstedt method is used throughout with all the literal algebraic manipulations being computerized so that all expansions are carried to the fourth order in the small parameter ε.

It is shown that each of the two normal modes of oscillation has a bifurcation (really trifurcation) point which moves towards the origin when the exact resonance is approached, explaining why the one-to-one resonant Contopoulos system has six modes of periodic oscillations near the origin, rather then the usual number of two.

We give a single Lindstedt-type literal expansion which is valid for the three intersecting families of periodic solutions. This expansion contains two constants, A and D, representing the direct and retrograde circulations C⁺ and C⁻ when both constants are non-zero and the vertical normal mode family when A = 0.

The verifications of the analytical results by numerical integrations are also given.     

Similarity-based ranking and query processing in multimedia databases

Since media-based evaluation yields similarity values, results to a multimedia database query, Q(Y₁,…,Y_n), is defined as an ordered list S_Q of n-tuples of the form X₁,…,X_n. The query Q itself is composed of a set of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, S_Q includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we first focus on the problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful final ranking”. More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, finding an efficient way to process the query.” We develop an algorithm to efficiently process queries with unordered fuzzy predicates (sub-queries). Although this algorithm can work with different fuzzy semantics, it benefits from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.     

Assignment of Complete Structural Properties of Linear Systems via Sensor Selection

For x =Ax + Bu , the problem of structural assignment via sensor selection is to find an output equation, y = Cx + Du , such that the resulting system (A, B, C, D) has the pre-specified structural properties, such as the finite and infinite zero structures as well as the invertibility properties. In this paper, we establish a set of necessary and sufficient conditions under which a complete set of system structural properties can be assigned, and an explicit algorithm for constructing the required matrix pair (C, D).     

Properties of Noncentral Dirichlet Distributions

Let X₁,…, X_r+1 be independent random variables, X_iGa (a_i, θ, δ_i), i = 1,…, r + 1. Define and V_i = X_i/X_r+1, i = 1,…, r. Then, (U₁,…, U_r) and (V₁,…, V_r) follow noncentral Dirichlet Type 1 and Type 2 distributions, respectively. In this article several properties of these distributions and their connections with the uniform, the noncentral multivariate-F and the noncentral multivariate-t distributions are discussed.     

Finding hidden independent sets in interval graphs

We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) independent set X by making the fewest queries of the form “Is point p covered by an interval in X?” Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.