共查询到20条相似文献,搜索用时 46 毫秒
1.
We define a self-map Pal:F2→F2 of the free group on two generators a,b, using automorphisms of F2 that form a group isomorphic to the braid group B3. The map Pal restricts to de Luca’s right iterated palindromic closure on the submonoid generated by a,b. We show that Pal is continuous for the profinite topology on F2; it is the unique continuous extension of de Luca’s right iterated palindromic closure to F2. The values of Pal are palindromes and coincide with the elements g∈F2 such that abg and bag are conjugate. 相似文献
2.
3.
4.
We present algorithmic lower bounds on the size sd of the largest independent sets of vertices in random d-regular graphs, for each fixed d≥3. For instance, for d=3 we prove that, for graphs on n vertices, sd≥0.43475n with probability approaching one as n tends to infinity. 相似文献
5.
Question/Answer games (Q/A games for short) are a generalization of the Rényi–Ulam game and they are a model for information extraction in parallel. A Q/A game, G=(D,s,(q1,…,qk)), is played on a directed acyclic graph, D=(V,E), with a distinguished start vertex s. In the ith round, Paul selects a set, Qi⊆V, of at most qi non-terminal vertices. Carole responds by choosing an outgoing edge from each vertex in Qi. At the end of k rounds, Paul wins if Carole’s answers define a unique path from the root to one of the terminal vertices in D. 相似文献
6.
Taisuke Izumi Akinori Saitoh Toshimitsu Masuzawa 《Journal of Parallel and Distributed Computing》2007
The Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ (Δ-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ-timed uniform consensus problem in presence of fc crash processes and ft timing-faulty processes, and propose a Δ-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ-timed uniform consensus when at least ft+1 correct processes exist in the system. If the system has less than ft+1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as ft+1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes requires that the system has at least ft+1 correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than ft+1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness. 相似文献
7.
A collection of T1,T2,…,Tk of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible if there exists a tree T such that each tree Ti can be obtained from T by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(nk) time, n being the number of leaves. Here, we present an O(nf(k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable (FPT) with respect to the number k of trees. 相似文献
8.
A real x is called h-bounded computable , for some function h:N→N, if there is a computable sequence (xs) of rational numbers which converges to x such that, for any n∈N, at most h(n) non-overlapping pairs of its members are separated by a distance larger than 2-n. In this paper we discuss properties of h-bounded computable reals for various functions h. We will show a simple sufficient condition for a class of functions h such that the corresponding h-bounded computable reals form an algebraic field. A hierarchy theorem for h-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h-bounded computability for special functions h. 相似文献
9.
We investigate a periodic version of the Benjamin-Ono (BO) equation associated with a discrete Laplacian. We find some special solutions to this equation, and calculate the values of the first two integrals of motion I1 and I2 corresponding to these solutions. It is found that there exists a strong resemblance between them and the spectra for the Macdonald q-difference operators. To better understand the connection between these classical and quantum integrable systems, we consider the special degenerate case corresponding to q=0 in more detail. Namely, we give general solutions to this degenerate periodic BO, obtain explicit formulas representing all the integrals of motions In (n=1,2,…), and successfully identify it with the eigenvalues of Macdonald operators in the limit q→0, i.e. the limit where Macdonald polynomials tend to the Hall–Littlewood polynomials. 相似文献
10.
Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many different settings. The input consists of a set I={r1,…,rn} of d-dimensional rectangular items ri=(ai,1,…,ai,d) and a space Q. The task is to pack the items in an orthogonal and non-overlapping manner without using rotations into the given space. In the strip packing setting the space Q is given by a strip of bounded basis and unlimited height. The objective is to pack all items into a strip of minimal height. In the knapsack packing setting the given space Q is a single, usually unit sized bin and the items have associated profits pi. The goal is to maximize the profit of a selection of items that can be packed into the bin. 相似文献
11.
We study the problem of decomposing the vertex set V of a graph into two nonempty parts V1,V2 which induce subgraphs where each vertex v∈V1 has degree at least a(v) inside V1 and each v∈V2 has degree at least b(v) inside V2. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible. 相似文献
12.
13.
Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has a demand d(v)∈Z+ and a cost c(v)∈R+, where Z+ and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G requires finding a set S of vertices minimizing ∑v∈Sc(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v∈V−S. It is known that if there exists a vertex v∈V with d(v)≥4, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(|V|4log2|V|) time if d(v)≤3 holds for each vertex v∈V. 相似文献
14.
Oleg Golubitsky Marina Kondratieva Marc Moreno Maza Alexey Ovchinnikov 《Journal of Symbolic Computation》2008
We consider the Rosenfeld–Gröbner algorithm for computing a regular decomposition of a radical differential ideal generated by a set of ordinary differential polynomials in n indeterminates. For a set of ordinary differential polynomials F, let M(F) be the sum of maximal orders of differential indeterminates occurring in F. We propose a modification of the Rosenfeld–Gröbner algorithm, in which for every intermediate polynomial system F, the bound M(F)?(n−1)!M(F0) holds, where F0 is the initial set of generators of the radical ideal. In particular, the resulting regular systems satisfy the bound. Since regular ideals can be decomposed into characterizable components algebraically, the bound also holds for the orders of derivatives occurring in a characteristic decomposition of a radical differential ideal. 相似文献
15.
We aim at finding the best possible seed values when computing a1/p using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a) in the interval [amin,amax], by building the sequence xn defined by the Newton–Raphson iteration, the natural choice consists in choosing x0 equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between x0 and f(a). And yet, if we perform n iterations, what matters is to minimize the maximum possible distance between xn and f(a). In several examples, the value of the best starting point varies rather significantly with the number of iterations. 相似文献
16.
We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn) memory for a list of size n, the i’th back-step from the farthest point reached so far takes O(lgi) time in the worst case, while the overhead per forward step is at most ? for arbitrary small constant ?>0. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k vs. kn1/k and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n1/k-ary, tree that can only be traversed in a pre-order fashion. 相似文献
17.
18.
We study the state complexity of certain simple languages. If A is an alphabet of k letters, then a k-language is a nonempty set of words of length k, that is, a uniform language of length k. We show that the minimal state complexity of a k-language is k+2, and the maximal, (kk−1−1)/(k−1)+2k+1. We prove constructively that, for every i between the minimal and maximal bounds, there is a language of state complexity i. We introduce a class of automata accepting sets of words that are permutations of A; these languages define a complete hierarchy of complexities between k2−k+3 and 2k+1. The languages of another class of automata, based on k-ary trees, define a complete hierarchy of complexities between 2k+1 and (kk−1−1)/(k−1)+2k+1. This provides new examples of uniform languages of maximal complexity. 相似文献
19.
Alix L.H. Chow Leana Golubchik Samir Khuller Yuan Yao 《Journal of Parallel and Distributed Computing》2012
We consider the following basic question: a source node wishes to stream an ordered sequence of packets to a collection of receivers, which are in K clusters. A node may send a packet to another node in its own cluster in one time step and to a node in a different cluster in Tc time steps (Tc>1). Each cluster has two special nodes. We assume that the source and the special nodes in each cluster have a higher capacity and thus can send multiple packets at each step, while all other nodes can both send and receive a packet at each step. We construct two (intra-cluster) data communication schemes, one based on multi-trees (using a collection of d-ary interior-disjoint trees) and the other based on hypercubes. The multi-tree scheme sustains streaming within a cluster with O(dlogN) maximum playback delay and O(dlogN) size buffers, while communicating with O(d) neighbors, where N is the maximum size of any cluster. We also show that this protocol is optimal when d=2 or 3. The hypercube scheme sustains streaming within a cluster, with O(log2(N)) maximum playback delay and O(1) size buffers, while communicating with O(log(N)) neighbors, for arbitrary N. In addition, we extend our multi-tree scheme to work when receivers depart and arrive over time. We also evaluate our dynamic schemes using simulations. 相似文献