Two theorems concerning recognizable N-subsets of σ1

It is proved that the family of recognizable N-subsets is not closed under the operation sup, and that there exists even a DOL length sequence x₀, x₁, … such that, for any k,x_i ? x_i+1 ? … ? x_i+k holds true for some i and the cardinality of the set {n ∈ N|x_n > x_n+1} is infinite.     

Choosing,Agreeing, and Eliminating in Communication Complexity

We consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are k fixed Boolean functions f ₁,…,f _k and each of Alice and Bob has k inputs, x ₁,…,x _k and y ₁,…,y _k , respectively. In the eliminate problem, Alice and Bob should output a vector σ₁,…,σ _k such that f _i (x _i , y _i ) ≠ σ _i for at least one i (i.e., their goal is to eliminate one of the 2 ^k output vectors); in the choose problem, Alice and Bob should return (i, f _i (x _i , y _i )), for some i (i.e., they choose one instance to solve), and in the agree problem they should return f _i (x _i , y _i ), for some i (i.e., if all the k Boolean values agree then this must be the output). The question, in each of the three cases, is whether one can do better than solving one (say, the first) instance. We study these three problems and prove various positive and negative results. In particular, we prove that the randomized communication complexity of eliminate, of k instances of the same function f, is characterized by the randomized communication complexity of solving one instance of f.     

Fine structure of a one-dimensional discrete point system

We consider a system of N points x ₁ < ... < x _N on a segment of the real line. An ideal system (crystal) is a system where all distances between neighbors are the same. Deviation from idealness is characterized by a system of finite differences ? _i ¹ = x _x+1 ? x _i , ? _i ^k+1 = ? _i+1 ^k ? ? _i ^k , for all possible i and k. We find asymptotic estimates as N ?? ??, k????, for a system of points minimizing the potential energy of a Coulomb system in an external field.     

On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n?2+ [lgn], andW _k (n) = n + (k?1)lg n +O(1) for all fixed k ≥ 3. In this paper we studyW′ _k (n), the minimax complexity of selecting thek largest, when tests of the form “Isx _i the median of {x _i ,x _j ,x _t }?” are also allowed. It is proved thatW′₂(n) =n?2+ [lgn], andW′ _k (n) =n + (k?1)lg₂ n +O(1) for all fixedk≥3.     

Fast error estimates for indirect measurements: applications to pavement engineering

In many real-life situations, we have the following problem: we want to know the value of some characteristicy that is difficult to measure directly (e.g., lifetime of a pavement, efficiency of an engine, etc.). To estimatey, we must know the relationship betweeny and some directly measurable physical quantitiesx ₁,...,x _n . From this relationship, we extract an algorithmf that allows us, givenx _i , to computey: y=f(x ₁, ...,x _n ). So, we measurex _i , apply an algorithmf, and get the desired estimate. Existing algorithms for error estimate (interval mathematics, Monte-Carlo methods, numerical differentiation, etc.) require computation time that is several times larger than the time necessary to computey=f(x ₁, ...,x _n ). So, if an algorithmf is already time-consuming, error estimates will take too long. In many cases, this algorithmf consists of two parts: first, we usex _i to determine the parametersz _k of a model that describes the measured object, and second, we use these parameters to estimatey. The most time-consuming part is findingz _k ; this is done by solving a system of non-linear equations; usually least squares method is used. We show that for suchf, one can estimate errors repeating this time-consuming part off only once. So, we can compute bothy and an error estimate fory with practically no increase in total computation time. As an example of this methodology, we give pavement lifetime estimates.     

The periodic nature of the positive solutions of a nonlinear fuzzy max-difference equation

We investigate the periodic nature of the positive solutions of the fuzzy difference equation , where k, m are positive integers, A₀, A₁, are positive fuzzy numbers and the initial values x_i, i = −d, −d + 1, … , −1, d = max{k, m}, are positive fuzzy numbers. In addition, we give conditions so that the solutions of this equation are unbounded.     

The probability of “undefined” (non-converging) output in generating the universal probability distribution

In order to generate a universal probability distribution to extrapolate a binary string x of length i, we feed random bits into a universal device, M. When we find an input string that gives an output matching x, we continue the successful input with random bits until M produces a zero or one as output. The relative probabilities of these two continuations can give a normalized prediction for the probability of the symbol following x. There is, however, a probability, Pi+1(u) that the continued random input string will not generate any output for the (i+1)th symbol.We will show . Here Eμ is the expected value with respect to μ, the probability distribution that created x. kμ is the Kolmogorov complexity of μ with respect to M. n is any positive integer. Usually we do not know μ and so we do not know kμ. However, if μ is the uniform distribution, we can usually find a good upper bound for kμ.     

Fitting a least squares piecewise linear continuous curve in two dimensions

An optimal piecewise linear continuous fit to a given set of n data points D = {(x_i, y_i) : 1 ≤ i ≤ n} in two dimensions consists of a continuous curve defined by k linear segments {L₁, L₂,…,L_k} which minimizes a weighted least squares error function with weight w_i at (x_i, y_i), where k ≥ 1 is a given integer. A key difficulty here is the fact that the linear segment L_j, which approximates a subset of consecutive data points D_j ⊂ D in an optimal solution, is not necessarily an optimal fit in itself for the points D_j. We solve the problem for the special case k = 2 by showing that an optimal solution essentially consists of two least squares linear regression lines in which the weight w_j of some data point (x_j, y_j) is split into the weights λw_j and (1 − λ)w_j, 0 ≤ λ ≤ 1, for computations of these lines. This gives an algorithm of worst-case complexity O(n) for finding an optimal solution for the case k = 2.     

Finite-State Unification Automata and Relational Languages

We define the new notion of a (finite-state) unification automaton, a device for finite-state recognition of relational languages by means of unification transitions. Words in such a language are formed by composing base relations, and have the general form r_i1(x_j1, x_k1)···r_in(x_jn, x_kn) for some n. Generation of such languages by regarding Horn clauses as grammers has been considered before, but to the best of our knowledge, recognizing such languages by suitably designed automata is a new approach. The main result presented is a pumping lemma, forming a necessary condition for finite-state recognizability. Some example results about such automata are given.     

On the time-space tradeoff for sorting with linear queries

Extending a result of Borodin et al. [1], we show that any branching program using linear queries “∑_iλ_ix_i:c” to sort n numbers x₁, x₂,…,x_n must satisfy the time-space tradeoff relation $\text{TS = Ω(n}{}^2\text{)}$. The same relation is also shown to be true for branching programs that uses queries “min R = ?” where R is any subset of {x₁, x₂,…,x_n}.     

On plane spanning trees and cycles of multicolored point sets with few intersections

Let P₁,…,Pk be a collection of disjoint point sets in R² in general position. We prove that for each 1?i?k we can find a plane spanning tree Ti of Pi such that the edges of T₁,…,Tk intersect at most , where n is the number of points in P₁∪?∪Pk. If the intersection of the convex hulls of P₁,…,Pk is nonempty, we can find k spanning cycles such that their edges intersect at most (k−1)n times, this bound is tight. We also prove that if P and Q are disjoint point sets in general position, then the minimum weight spanning trees of P and Q intersect at most 8n times, where |P∪Q|=n (the weight of an edge is its length).     

An informal introduction to a high level language with applications to interval mathematics

The main problem of interval computations is as follows:given sets of possible valuesX _i for variablesx _i, and an algorithmf:R ⁿ → R, to.estimate the rangef(X ₁, ..,X _n ) of the possible values off(x ₁, ...,x _n ). In many real-life, situations setsX _i are not intervals. To handle such problems, it is desirable to add set data type and operations with sets to a programming language. it is well known that the entire mathematics can be formulated in terms of sets. So, if we already have a set as a data type, why have anything else. The main reason, is that expression in terms of sets is often clumsy. To avoid this clumsiness, it has been suggested to use not only sets, but alsobags (multisets), in which an element can have multiple occurrences. Bags are used in many areas of Computer Science, and recently, several languages have appeared that use the bag as a basic data type. In this paper, we explain the main ideas behind bag languages, and we also show:

· that bag languages are naturally parallelizable, thus leading to a parallelization of the coresponding generalized interval computations;

· and that bag languages can be also helpfully applied to traditional interval computations (where setsX _i are intervals).

     

On the <Emphasis Type="Italic">k</Emphasis>-accessibility of cores of <Emphasis Type="Italic">TU</Emphasis>-cooperative games

This paper proposes a strengthening of the author’s core-accessibility theorem for balanced TU-cooperative games. The obtained strengthening relaxes the influence of the nontransitivity of classical domination αv on the quality of the sequential improvement of dominated imputations in a game v. More specifically, we establish the k-accessibility of the core C(α _v ) of any balanced TU-cooperative game v for all natural numbers k: for each dominated imputation x, there exists a converging sequence of imputations x₀, x₁,..., such that x₀ = x, lim x _r ∈ C(α _v ) and x_r?m is dominated by any successive imputation x _r with m ∈ [1, k] and r ≥ m. For showing that the TU-property is essential to provide the k-accessibility of the core, we give an example of an NTU-cooperative game G with a ”black hole” representing a nonempty closed subset B ? G(N) of dominated imputations that contains all the α _G -monotonic sequential improvement trajectories originating at any point x ∈ B.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

A combinatorial algorithm for max csp

We consider the problem max csp over multi-valued domains with variables ranging over sets of size s_i?s and constraints involving k_j?k variables. We study two algorithms with approximation ratios A and B, respectively, so we obtain a solution with approximation ratio max(A,B).The first algorithm is based on the linear programming algorithm of Serna, Trevisan, and Xhafa [Proc. 15th Annual Symp. on Theoret. Aspects of Comput. Sci., 1998, pp. 488-498] and gives ratio A which is bounded below by s^1−k. For k=2, our bound in terms of the individual set sizes is the minimum over all constraints involving two variables of , where s₁ and s₂ are the set sizes for the two variables.We then give a simple combinatorial algorithm which has approximation ratio B, with B>A/e. The bound is greater than s^1−k/e in general, and greater than s^1−k(1−(s−1)/2(k−1)) for s?k−1, thus close to the s^1−k linear programming bound for large k. For k=2, the bound is if s=2, 1/2(s−1) if s?3, and in general greater than the minimum of 1/4s₁+1/4s₂ over constraints with set sizes s₁ and s₂, thus within a factor of two of the linear programming bound.For the case of k=2 and s=2 we prove an integrality gap of . This shows that our analysis is tight for any method that uses the linear programming upper bound.