An Additivity Theorem for Plain Kolmogorov Complexity

We prove the formula C(a,b)=K(a|C(a,b))+C(b|a,C(a,b))+O(1) that expresses the plain complexity of a pair in terms of prefix-free and plain conditional complexities of its components.     

Nonreducible Descriptions for the Conditional Kolmogorov Complexity

Assume that a program p produces an output string b for an input string a: p(a) = b. We look for a “reduction” (simplification) of p, i.e., a program q such that q(a) = b but q has Kolmogorov complexity smaller than p and contains no additional information as compared to p (this means that the conditional complexity K(q|p) is negligible). We show that, for any two strings a and b (except for some degenerate cases), one can find a nonreducible program p of any arbitrarily large complexity (any value larger than K(a) + K(b|a) is possible).     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.     

Uniqueness of reconstruction for Yager's t‐norm combination of probabilistic and possibilistic knowledge

Often, about the same real‐life system, we have both measurement‐related probabilistic information expressed by a probability measure P(S) and expert‐related possibilistic information expressed by a possibility measure M(S). To get the most adequate idea about the system, we must combine these two pieces of information. For this combination, R. Yager—borrowing an idea from fuzzy logic—proposed to use a t‐norm f_&(a,b) such as the product f_&(a,b)=a· b, i.e., to consider a set function f(S)=f_&(P(S),M(S)). A natural question is: can we uniquely reconstruct the two parts of knowledge from this function f(S)? In our previous paper, we showed that such a unique reconstruction is possible for the product t‐norm; in this paper, we extend this result to a general class of t‐norms. © 2011 Wiley Periodicals, Inc.     

Stochastic stabilization and destabilization

It is shown in this paper that any nonlinear systems in ^d can be stabilized by Brownian motion provided |ƒ(x,t)| ≤ K|x| for some K > 0. On the other hand, this system can also be destabilized by Brownian motion if the dimension d ≥ 2. Similar results are also obtained for any given stochastic differential equation dx(t) = ƒ(x(t), t) + g(x(t), t) dW(t).     

Stability of properties of Kolmogorov complexity under relativization

Assume that a tuple of binary strings \(\bar a\) = 〈a ₁ ..., a _n 〉 has negligible mutual information with another string b. Does this mean that properties of the Kolmogorov complexity of \(\bar a\) do not change significantly if we relativize them to b? This question becomes very nontrivial when we try to formalize it. In this paper we investigate this problem for a special class of properties (for properties that can be expressed by an ?-formula). In particular, we show that a random (conditional on \(\bar a\)) oracle b does not help to extract common information from the strings a _i .     

Local noncuppability in R/M

Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a]≤[c]and [a] ∨ [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ] ∈R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [c] and[d].     

Isolation, Infima and Diamond Embeddings

In (1993, Annals of Pure and Applied Logic, 62, 207–263),Kaddah pointed out that there are two d.c.e. degrees a,b forminga minimal pair in the d.c.e. degrees, but not in the degrees. Kaddah's; result shows thatLachlan's; theorem, stating that the infima of two c.e. degreesin the c.e. degrees and in the degrees coincide, cannot be generalized to the d.c.e. degrees. In this article, we apply Kaddah's; idea to show that thereare two d.c.e. degrees c,d such that c cups d to 0', and capsd to 0 in the d.c.e. degrees, but not in the degrees. As a consequence, the diamond embedding{0,c,d,0'} is different from the one first constructed by Downeyin 1989 in [5]. To obtain this, we will construct c.e. degreesa,b, d.c.e. degrees c > a,d > b and a non-zero -c.e. degreee c,d such that (i) a,b form a minimal pair, (ii) a isolatesc, and (iii) b isolates d. From this, we can have that c,d forma minimal pair in the d.c.e. degrees, and Kaddah's; result followsimmediately. In our construction, we apply Kaddah's; originalidea to make e below both c and d. Our construction allows usto separate the minimal pair argument (ab = 0), the splittingof 0' (cd = 0'), and the non-minimal pair of c,d (in the degrees), into several parts, to avoiddirect conflicts that could be involved if only c,d and e areconstructed. We also point out that our construction allowsus to make a,b above (and hence c,d) high.     

Inequalities for the Number of Walks in Graphs

We investigate the growth of the number w _k of walks of length k in undirected graphs as well as related inequalities. In the first part, we deduce the inequality w _2a+c ?w _2(a+b)+c ≤w _2a ?w _2(a+b+c), which we call the Sandwich Theorem. It unifies and generalizes an inequality by Lagarias et al. and an inequality by Dress and Gutman. In the same way, we derive the inequality w _2a+c (v,v)?w _2(a+b)+c (v,v)≤w _2a (v,v)?w _2(a+b+c)(v,v) for the number w _k (v,v) of closed walks of length k starting at a given vertex v. We then use a theorem of Blakley and Dixon to show $w_{2\ell+p}^{k}\leq w_{2\ell+pk}\cdot w_{2\ell}^{k-1}$ , which unifies and generalizes an inequality by Erd?s and Simonovits and, again, the inequality by Dress and Gutman. Both results can be translated directly into the corresponding forms using the higher order densities, which extends former results. In the second part, we provide a new family of lower bounds for the largest eigenvalue λ ₁ of the adjacency matrix based on closed walks. We apply the Sandwich Theorem to show monotonicity in this and a related family of lower bounds of Nikiforov. This leads to generalized upper bounds for the energy of graphs. In the third part, we demonstrate that a further natural generalization of the Sandwich Theorem is not valid for general graphs. We show that the inequality w _a+b ?w _a+b+c ≤w _a ?w _a+2b+c does not hold even in very restricted cases like w ₁?w ₂≤w ₀?w ₃ (i.e., $\bar{d}\cdot w_{2}\leq w_{3}$ ) in the context of bipartite or cycle free graphs. In contrast, we show that surprisingly this inequality is always satisfied for trees and we show how to construct worst-case instances (regarding the difference of both sides of the inequality) for a given degree sequence. We also prove the inequality w ₁?w ₄≤w ₀?w ₅ (i.e., $\bar{d}\cdot w_{4}\leq w_{5}$ ) for trees and conclude with a corresponding conjecture for longer walks.     

Cataloguing/analogizing: A nonmonotonic view

Reasoning deductively under incomplete information is nonmonotonic in nature since the arrival of additional information may invalidate or reverse previously obtained conclusions. It amounts to apply generic default rules in an appropriate way to a particular (partially described) situation. This type of nonmonotonic reasoning can only provide plausible conclusions. Analogical reasoning is another form of commonly used reasoning that yields brittle conclusions. It is nondeductive in nature and proceeds by putting particular situations in parallel. Analogical reasoning also exhibits nonmonotonic features, as investigated in this paper when particular situations may be incompletely stated. The paper reconsiders the pattern of plausible reasoning proposed by Polya, “a and b are analogous, a is true, then b true is more credible,'' from a nonmonotonic reasoning point of view. A representation of the statement “a and b are analogous” in terms of nonmonotonic consequences relations is presented. This representation is then related to a logical definition of analogical proportions, i.e. statements of the form “a is to b as c is to d” that has been recently proposed and extended to other types of proportions. Remarkably enough, semantic equivalence between conditional objects of the form “b given a,” which have been shown as being at the root of nonmonotonic reasoning, constitutes another type of noticeable proportions. By offering a parallel between two important forms of commonsense reasoning, this paper enriches the comparison between nonmonotonic reasoning and analogical reasoning that is not often made. © 2011 Wiley Periodicals, Inc.     

Relaxing the Triangle Inequality in Pattern Matching

Any notion of closeness in pattern matching should have the property that if A is close to B, and B is close to C, then A is close to C. Traditionally, this property is attained because of the triangle inequality (d(A, C) d(A, B) + d(B, C), where d represents a notion of distance). However, the full power of the triangle inequality is not needed for this property to hold. Instead, a relaxed triangle inequality suffices, of the form d(A, C) c(d(A, B) + d(B, C)), where c is a constant that is not too large. In this paper, we show that one of the measures used for distances between shapes in (an experimental version of) IBM's QBIC¹ ("Query by Image Content") system (Niblack et al., 1993) satisfies a relaxed triangle inequality, although it does not satisfy the triangle inequality.     

The number of pessimistic guesses in Generalized Black-peg Mastermind

Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible using information he receives from the codemaker after each guess. In Generalized Black-peg Mastermind for given arbitrary numbers p, c, the secret code consists of p pegs each having one of c colors, and the received information consists only of a number of black pegs, where this number equals the number of pegs matching in the corresponding question and the secret code. Let b(p,c) be the pessimistic number of questions for Generalized Black-peg Mastermind. By a computer program we compute several values b(p,c). By introducing some auxiliary games and combining this program with theoretical methods, for arbitrary c we obtain exact formulas for b(2,c), b(3,c) and b(4,c) and give upper and lower bounds for b(5,c) and a lower bound for b(6,c). Furthermore, for arbitrary p, we present upper bounds for b(p,2), b(p,3) and b(p,4). Finally, we give bounds for the general case b(p,c). In particular, we improve an upper bound recently proved by Goodrich.     

Linguistic hedges and the generalized modus ponens

In this paper a modification of the generalized modus ponens is presented, namely, rule: if X is bB then Y is cC; fact: X is aB, conclusion: Y is dC where a, b, c, e, and d are linguistic hedges, and B, C are fuzzy sets. The procedure that allows one to evaluate the modifier d is very simple and gives results given in Refs. 15, 18, 26, and 27. Our approach is algebraic-based and realizes Zadeh's calculus on words by means of Chang's MV algebra. ©1999 John Wiley & Sons, Inc.     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

Worst-case optimal algorithm for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D; i.e., determine the set Q(D) of document elements selected by Q. We mainly consider Conjunctive XPath queries that involve only the child and descendant axes. Previously known in-memory algorithms for this problem use O(|D|) space and O(|Q||D|) time. Several previously known algorithms for the streaming version use Ω(dn) space and Ω(dn|D|) time in the worst case; d denotes the depth of D, and n denotes the number of location steps in Q. Their exponential space requirement could well exceed the O(|D|) space used by the in-memory algorithms. We present an efficient algorithm that uses O(d|Q|+nc) space and O((|Q|+dn)|D|) time in the worst case; c denotes the maximum number of elements of D that can be candidates for output, at any one instant. For some worst case Q and D, the memory space used by our algorithm matches our lower bound proved in a different paper; so, our algorithm uses optimal memory space in the worst case.     

New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph

We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|²) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.     

Some new paranormed sequence spaces

Maddox defined the sequence spaces ℓ_∞(p), c(p) and c₀(p) in [Proc. Camb. Philos. Soc. 64 (1968) 335, Quart. J. Math. Oxford (2) 18 (1967) 345]. In the present paper, the sequence spaces a₀^r(u,p) and a_c^r(u,p) of non-absolute type have been introduced and proved that the spaces a₀^r(u,p) and a_c^r(u,p) are linearly isomorphic to the spaces c₀(p) and c(p), respectively. Besides this, the α-, β- and γ-duals of the spaces a₀^r(u,p) and a_c^r(u,p) have been computed and their basis have been constructed. Finally, a basic theorem has been given and later some matrix mappings from a₀^r(u,p) to the some sequence spaces of Maddox and to some new sequence spaces have been characterized.     

Naive Bayes for value difference metric

The value difference metric (VDM) is one of the best-known and widely used distance functions for nominal attributes. This work applies the instanceweighting technique to improveVDM. An instance weighted value difference metric (IWVDM) is proposed here. Different from prior work, IWVDM uses naive Bayes (NB) to find weights for training instances. Because early work has shown that there is a close relationship between VDM and NB, some work on NB can be applied to VDM. The weight of a training instance x, that belongs to the class c, is assigned according to the difference between the estimated conditional probability ^P(c|x) by NB and the true conditional probability P(c|x), and the weight is adjusted iteratively. Compared with previous work, IWVDM has the advantage of reducing the time complexity of the process of finding weights, and simultaneously improving the performance of VDM. Experimental results on 36 UCI datasets validate the effectiveness of IWVDM.     

On closed-form approximations for the free energy ofd-dimensional Ising model,II

It has been shown that it is possible to construct families of closed-form approximations lnZ* _d to lnZ _d for the anisotropic Ising model on ad-dimensional hypercubical lattice whose high- and low-temperature series expansions coincide with the corresponding exact expansions up to some order. For the isotropic case the density of zeros ofZ* _d near the critical pointK _c is found under the assumption that they behave like sinh2K=±(sinh2K _c +y±iy). It is shown that there exists a family of closed-form approximations such that ford3 the only possible densities of zeros arem(y)=|y|³ for=0 andm(y)=|y| for 0<||1, i.e., it contains the exact case ford5 corresponding to ||=1.