Reductions between disjoint NP-Pairs

Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A B, then all queries belong to C D. We prove under the reasonable assumption that UP ∩ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.     

On γ-reducibility versus polynomial time many-one reducibility

We prove that each element of a class of functions (denoted by NPC_t^P), whose graphs can be accepted in nondeterministic polynomial time, can be evaluated in deterministic polynomial time if and only if γ-reducibility is equivalent to polynomial time many-one reducibility. We also modify the proof technique used to obtain part of this result to obtain the stronger result that if every γ-reduction can be replaced by a polynomial time Turing reduction, then every function in NPC_t^P can be evaluated in deterministic polynomial time.     

Computing maximal Kleene closures that are embeddable in a given subword-closed language

Motivated by certain coding techniques for reliable DNA computing, we consider the problem of characterizing nontrivial languages D that are maximal with the property that D ^* is contained in the subword closure of a given set S of words of some fixed length k. This closure is simply the set of all words whose subwords of length k must be in S. We provide a deep structural characterization of these languages D, which leads to polynomial time algorithms for computing such languages.     

Maximal c consensus meets

Given a set S of subsets of a reference set X, we define the problem of finding c subsets of X that maximize the size of the intersection among the included subsets. Maximizing the size of the intersection means that they are subsets of the sets in S and they are as large as possible.We can understand the result of this problem as c consensus sets of S, or c consensus representatives of S. From the perspective of lattice theory, each representative will be a meet of some sets in S.In this paper we define formally this problem, and present heuristic algorithms to solve it. We also discuss the relationship with other established problems in the literature.     

Restricted arc-connectivity of digraphs

Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ^′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ^′-connected, if λ^′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ^′-connected and satisfies λ^′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D₁ such that D−V(D₁) contains an arc. The restricted arc-connectivity λ^′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ^′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results.     

A note on ‘geometric transforms’ of digital sets

We define a ‘geometric transform’ on the digital plane as a function ? that takes pairs (P, S), where S is a set and P a point of S, into nonnegative integers, and where $\text{?(S, P)}$ depends only on the positions of the points of S relative to P. Transforms of this type are useful for segmenting and describing S. Two examples are ‘distance transforms’, for which $\text{?(S, P)}$ is the distance from P to S, and ‘isovist transforms’, where $\text{?(S, P)}$, is the area of the part S visible from P. This note characterizes geometric transforms that have certain simple set-theoretic properties, e.g., such that $\text{?(S?T,P) = ?(S,P)∧?(T,P)}$ for all S, T, P. It is shown that a geometric transform has this intersection property if and only if it is defined in a special way in terms of a ‘neighborhood base’; the class of such ‘neighborhood transforms’ is a generalization of the class of distance transforms.     

On the diameter of geometric path graphs of points in convex position

For a set S of n points in convex position in the plane, let P(S) denote the set of all plane spanning paths of S. The geometric path graph of S, denoted by Gn, is the graph with P(S) as its vertex set and two vertices P,Q∈P(S) are adjacent if and only if P and Q can be transformed to each other by means of a single edge replacement. Recently, Akl et al. [S.G. Akl, K. Islam, H. Meijer, On planar path transformation, Inform. Process. Lett. 104 (2007) 59-64] showed that the diameter of Gn is at most 2n−5. In this note, we derive the exact diameter of Gn for n?3.     

Efficient and accurate computation of geometric moments on gray-scale images

A novel algorithm that permits the fast and accurate computation of geometric moments on gray-scale images is presented in this paper. The proposed algorithm constitutes an extension of the IBR algorithm, introduced in the past, which was applicable only for binary images. A new image representation scheme, the ISR (intensity slice representation), which represents a gray-scale image as an expansion of several two-level images of different intensity values, enables the partially application of the IBR algorithm to each image component. Moreover, using the resulted set of image blocks, the geometric moments’ computation can be accelerated through appropriate computation schemes.     

A Protocol for a Private Set-Operation

A new private set-operation problem is proposed. Suppose there are n parties with each owning a secret set. Let one of them, say P, be the leader, S be P＇s secret set, and t （less than n - 1） be a threshold value. For each element w of S, if w appears more than t times in the rest parties＇ sets, then P learns which parties＇ sets include w, otherwise P cannot know whether w appears in any party＇s set. For this problem, a secure protocol is proposed in the semi-honest model based on semantically secure homomorphic encryption scheme, secure sharing scheme, and the polynomial representation of sets. The protocol only needs constant rounds of communication.     

Model-free frequency domain iterative active sound and vibration control

In this paper, a model-free iterative feedback tuning method is presented to tune a frequency domain controller for a set of narrow-band disturbances. A single control problem with multiple tones of the disturbance is split into a set of parallel control problems. Due to the representation in the frequency domain, there are only control amplitude and phase to be tuned for each tone. Tuning is performed through a sequence of experiments which enables the calculation of a model-free gradient of a quadratic cost function. The number of experiments at each iterative step is R×S+1, where R is the number of controls signals and S is the number of output signals. Results on a laboratory active sound control system are shown. The example demonstrates the practical effectiveness of the method.     

The computation of fourth virial coefficients for pairwise-additive spherically symmetric interaction potentials

A method is given for computing the fourth virial coefficient D(T) for a pairwise additive spherically symmetric interaction potential. Taking one of the four interacting particles as origin and using the appropriate co-ordinate transformations in the usual way the ninefold integrals defining D(T) are reduced to sixfold integrals which are then formally reduced to triple integrals by expanding out those Ursell-Mayer functions in the integrals not involving the origin particle as infinite series in Legendre polynomials P_S(cos?), where ? is the angle between the radius vectors of the interacting particles. The coefficients in these expansions are integrals of highly oscillatory functions, especially for large s, and are evaluated using the Chebyshev polynomial expansion for the Ursell-Mayer functions, thus making explicit use of the oscillatory behaviour of P_S(cos?). The triple integrals are evaluated using a nonproduct integration formula of the seventh degree employed earlier in the computation of the thirdh virial coefficient. The values of D(T) computed by the present method have the same qualitative behaviour as the literature values but appear to be more accurate, particularly at lower temperatures.     

The ‘Hoare logic’ of concurrent programs

Summary Hoare's logical system for specifying and proving partial correctness properties of sequential programs is generalized to concurrent programs. The basic idea is to define the assertion {P} S {Q} to mean that if execution is begun anywhere in S with P true, then P will remain true until S terminates, and Q will be true if and when S terminates. The predicates P and Q may depend upon program control locations as well as upon the values of variables. A system of inference rules and axiom schemas is given, and a formal correctness proof for a simple program is outlined. We show that by specifying certain requirements for the unimplemented parts, correctness properties can be proved without completely implementing the program. The relation to Pnueli's temporal logic formalism is also discussed.     

The possible cardinalities of global secure sets in cographs

Let G=(V,E) be a graph. A global secure set SD⊆V is a dominating set which also satisfies a condition that |N[X]∩SD|≥|N[X]−SD| for every subset X⊆SD. The minimum cardinality of the global secure set in the graph G is denoted by γ_s(G). In this paper, we introduce the notion of γ_s-monotone graphs. The graph G is γ_s-monotone if, for every k∈{γ_s(G),γ_s(G)+1,…,n}, it has a global secure set of cardinality k. We will also present the results concerning the minimum cardinality of the global secure sets in the class of cographs.     

Graham triangulations and triangulations with a center are hamiltonean

Let P be a point set with n elements in general position. A triangulation T of P is a set of triangles with disjoint interiors such that their union is the convex hull of P, no triangle contains an element of P in its interior, and the vertices of the triangles of T are points of P. Given T we define a graph G(T) whose vertices are the triangles of T, two of which are adjacent if they share an edge. We say that T is hamiltonean if G(T) has a hamiltonean path. We prove that the triangulations produced by Graham's Scan are hamiltonean. Furthermore we prove that any triangulation T of a point set which has a point adjacent to all the points in P (a center of T) is hamiltonean.     

Approximate pattern matching in a pattern database system

This work is concerned with the organization of a large database of binary pictures (normalized for size, rotation and position) and with the efficient “inexact match” of an input pattern against the whole database. Current techniques in pattern analysis use matching algorithms without any regard to the global organization of the storage representations of the models they are to match. Consequently, the algorithms are only practical for small databases. This paper discusses the design of a pattern database system and the economy that it provides for the matching problem. The database organization is based on the quad-tree representation of binary patterns. Given an arbitrary decomposition D (or partition) of a pattern P and an arbitrary function f on the pattern, we repeatedly apply f on D(P), D(D(P))P, … to obtain higher and higher levels of abstraction f(D)(P)), f(D(D(P))), … of the pattern. The computed values obtained after the jth application of f are used to label the ith level of the pyramid. The specific representation used in this paper is called the sum-quad-tree, in which each level of the tree stores the sum of the labels of its sons. The lowest level of the sum-quad-tree corresponds to the individual pixels and is the nth level (i.e. node m at level n implies v(m) = 0 or v(m) = 1). Nodes at the jth level of the sum-quad-tree correspond to sums of 2^n?j × 2^n?j picture points, so that the 0th level contains the number of 1's in the pattern. The pyramid representation is used as a hierarchical (n-level) indexing scheme of the database. The advantage of this organization is that the matching algorithms presented reject most of the patterns in the database by utilizing the relatively small in size index tables and thus avoid the overhead of unnecessary CPU time and $\text{I}\text{O}$ operation between main memory and secondary storage.     

Average curve of n smooth planar curves

We define the Average Curve (AC) of a compatible set of two or more smooth and planar, Jordan curves. It is independent of their order and representation. We compare two variants: the valley AC (vAC), defined in terms of the valley of the field that sums the squared distances to the input curves, and the zero AC (zAC), defined as the zero set of the field that sums the signed distances to the input curves. Our formulation provides an orthogonal projection homeomorphism from the AC to each input curve. We use it to define compatibility. We propose a fast tracing algorithm for computing a polygonal approximation (PAC) of the AC and for testing compatibility. We provide a linear-cost implementation for tracing the PAC of polygonal approximations of smooth input curves. We also define the inflation of the AC and use it to visualize the local variability in the set of input curves. We argue that the AC and its inflation form a natural extension of the Medial Axis Transform to an arbitrary number of curves. We propose extensions to open curves and to weighted averages of curves, which can be used to design animations.     

Descendants of a recognizable tree language for sets of linear monadic term rewrite rules

For a tree language L and a set S of term rewrite rules over Σ, the descendant of L for S is the set S^∗(L) of trees reachable from a tree in L by rewriting in S. For a recognizable tree language L, we study the set D(L) of descendants of L for all sets of linear monadic term rewrite rules over Σ. We show that D(L) is finite. For each tree automaton A over Σ, we can effectively construct a set {R₁,…,Rk} of linear monadic term rewrite systems over Σ such that and for any 1?i<j?k, .     

Reductions to Graph Isomorphism

We show that several reducibility notions coincide when applied to the Graph Isomorphism (GI) problem. In particular we show that if a set is many-one logspace reducible to GI, then it is in fact many-one \(\textsf{AC}^{0}\) reducible to GI. For the case of Turing reducibilities we show that for any k≥0 an \(\textsf{NC}^{k+1}\) reduction to GI can be transformed into an \(\textsf{AC}^{k}\) reduction to the same problem.