waashk/dblp huggingface dataset:
dna duplex cage structures with icosahedral symmetry. a construction method for duplex cage structures with icosahedral symmetry made out of single-stranded dna molecules is presented and applied to an icosidodecahedral cage. it is shown via a mixture of analytic and computer techniques that there exist realisations of this graph in terms of two circular dna molecules. these blueprints for the organisation of a cage structure with a noncrystallographic symmetry may assist in the design of containers made from dna for applications in nanotechnology.
a constrained edit distance algorithm between semi-ordered trees. in this paper, we propose a formal definition of a new class of trees called semi-ordered trees and a polynomial dynamic programming algorithm to compute a constrained edit distance between such trees. the core of the method relies on a similar approach to compare unordered [kaizhong zhang, a constrained edit distance between unordered labeled trees, algorithmica 15 (1996) 205-222] and ordered trees [kaizhong zhang, algorithms for the constrained editing distance between ordered labeled trees and related problems, pattern recognition 28 (3) (1995) 463-474]. the method is currently applied to evaluate the similarity between architectures of apple trees [vincent segura, aida ouangraoua, pascal ferraro, evelyne costes, comparison of tree architecture using tree edit distances: application to two-year-old apple tree, euphytica 161 (2007) 155-164].
the complexity of small universal turing machines: a survey. we survey some work concerned with small universal turing machines, cellular automata, tag systems, and other simple models of computation. for example, it has been an open question for some time as to whether the smallest known universal turing machines of minsky, rogozhin, baiocchi and kudlek are efficient (polynomial time) simulators of turing machines. these are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. we discuss recent work that shows that these machines are indeed efficient simulators. as a related result, we also find that rule 110, a well-known elementary cellular automaton, is also efficiently universal. we also review a large number of old and new universal program size results, including new small universal turing machines and new weakly, and semi-weakly, universal turing machines. we then discuss some ideas for future work arising out of these, and other, results.
a topological treatment of early-deciding set-agreement. the k-set-agreement problem consists for a set of n processes to agree on less than k among n possibly different values, each initially known to only one process. the problem is at the heart of distributed computing and generalizes the celebrated consensus problem. this paper considers the k-set-agreement problem in a synchronous message passing distributed system where up to t processes can fail by crashing. we determine the number of communication rounds needed for all correct processes to reach a decision in a given run, as a function of the degree of coordination k and the number of processes that actually fail in the run, f@?t. we prove that, for any integer 1@?k
construction of strongly connected dominating sets in asymmetric multihop wireless networks. consider an asymmetric wireless network represented by a digraph g=(v,e). a subset of vertices u is called a strongly connected dominating set (scds) if the subgraph induced by u is strongly connected and every vertex not in u has both an in-neighbor in u and an out-neighbor in u. scds plays an important role of the virtual backbone in asymmetric wireless networks. motivated by the construction of a small virtual backbone, we study the problem minimum scds, which seeks a smallest scds of a digraph. for any constant 0
distributed algorithms for partitioning a swarm of autonomous mobile robots. a number of recent studies address systems of mobile autonomous robots from a distributed computing point of view. although such systems employ robots that are relatively weak and simple (i.e., dimensionless, oblivious and anonymous), they are nevertheless expected to have strong fault tolerance capabilities as a group. this paper studies the partitioning problem, where n robots must divide themselves into k size-balanced groups, and examines the impact of common orientation on the solvability of this problem. first, deterministic crash-fault-tolerant algorithms are given for the problem in the asynchronous full-compass and semi-synchronous half-compass models, and a randomized algorithm is given for the semi-synchronous no-compass model. next, the role of common orientation shared by the robots is examined. necessary and sufficient conditions for the partitioning problem to be solvable are given in the different timing models. finally, the problem is proved to be unsolvable in the no-compass synchronous model.
autonomous programmable dna nanorobotic devices using dnazymes. a major challenge in nanoscience is the design of synthetic molecular devices that run autonomously (that is, without externally mediated changes per work-cycle) and are programmable (that is, their behavior can be modified without complete redesign of the device). dna-based synthetic molecular devices have the advantage of being relatively simple to design and engineer, due to the predictable secondary structure of dna nanostructures and the well-established biochemistry used to manipulate dna nanostructures. however, ideally we would like to minimize the use of protein enzymes in the design of a dna-based synthetic molecular device. we present the design of a class of dna-based molecular devices using dnazyme. these dnazyme-based devices are autonomous, programmable, and further require no protein enzymes. the basic principle involved is inspired by a simple but ingenious molecular device due to tian et al. [y. tian, y. he, y. chen, p. yin, c. mao, a dnazyme that walks processively and autonomously along a one-dimensional track, angew. chem. intl. ed. 44 (2005) 4355-4358] that used dnazyme to traverse on a dna nanostructure, but was not programmable in the sense defined above (it did not execute computations). our dnazyme-based designs include (1) a finite state automaton, dnazyme fsa that executes finite state transitions using dnazymes, (2) extensions to it including probabilistic automaton and non-deterministic automaton, and (3) its application as a dnazyme router for programmable routing of nanostructures on a 2d dna addressable lattice. furthermore, we give a medical-related application, dnazyme doctor that provides transduction of nucleic acid expression: it can be programmed to respond to the underexpression or overexpression of various strands of rna, with a response by the release of an rna. (the behavior of our nucleic acid transduction devices is similar to those of the prior paper of benenson [y. benenson, b. gil, u. ben-dor, r. adar, e. shapiro, an autonomous molecular computer for logical control of gene expression, nature 429 (2004) 423-429], but ours have the advantage that they operate without the use of any protein enzymes.)
overlap-freeness in infinite partial words. we prove that there exist infinitely many infinite overlap-free binary partial words containing at least one hole. moreover, we show that these words cannot contain more than one hole and the only hole must occur either in the first or in the second position. we define that a partial word is k-overlap-free if it does not contain a factor of the form xyxyx where the length of x is at least k. we prove that there exist infinitely many 2-overlap-free binary partial words containing an infinite number of holes.
algorithms for connected set cover problem and fault-tolerant connected set cover problem. given a set v of elements, s a family of subsets of v, and g a connected graph on vertex set s,a connected set cover (csc) is a subfamily r of s such that every element in v is covered by at least one set of r, and the subgraph g[r] of g induced by r is connected. if furthermore g[r] is k-connected and every element in v is covered by at least m sets in r, then r is a (k,m)-csc. in this paper, we present two approximation algorithms for the minimum csc problem, and one approximation algorithm for the minimum (2,m)-csc problem. performance ratios are analyzed. these are the first approximation algorithms for csc problems in general graphs with guaranteed performance ratios.
local edge colouring of yao-like subgraphs of unit disk graphs. the focus of the present paper is on providing a local deterministic algorithm for colouring the edges of yao-like subgraphs of unit disk graphs. these are geometric graphs such that for some positive integers l,k the following property holds at each node v: if we partition the unit circle centered at v into 2k equally sized wedges then each wedge can contain at most l points different from v. we assume that the nodes are location aware, i.e. they know their cartesian coordinates in the plane. the algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k and l, but not on the size of the graph) number of hops (measured in the original underlying unit disk graph) away from it, and hence the algorithm terminates in a constant number of steps. the number of colours used is 2kl+1 and this is optimal for local algorithms (since the maximal degree is 2kl and a colouring with 2kl colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.
on the cost of uniform protocols whose memory consumption is adaptive to interval contention. recently, we introduced a novel term, memory-adaptive, whose goal it is to capture what it means for a distributed protocol to most efficiently make use of its shared memory. we proved three results that relate to the memory-adaptive model in the uniform setting. we considered a store/release protocol where processes are required to store a value in shared mwmr memory so that it cannot be overwritten until it has been released by the process. we showed that there do not exist uniformly wait-free store/release protocols using only the basic operations read and write that are memory-adaptive to point contention. we further showed that there exists a uniformly wait-free store/release protocol using only the basic operations read, write, and read-modify-write that is memory-adaptive to interval contention and time-adaptive to total contention. this left a significant gap - it remained open as to whether there exists a uniform, memory adaptive to interval contention store/release protocol that only uses read/write (no read-modify-write) registers. in this paper, we close this gap by showing that no such protocol can exist. we furthermore illustrate the validity and practicality of the concept of memory adaptiveness by providing a uniform, memory-adaptive to interval contention store/release protocol for network attached disks.
gathering few fat mobile robots in the plane. autonomous identical robots represented by unit discs move deterministically in the plane. they do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. gathering such robots means forming a configuration for which the union of all discs representing them is connected. we solve the gathering problem for at most four robots. this is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots fat.
convergence rates of markov chains for some self-assembly and non-saturated ising models. algorithms based on markov chains are ubiquitous across scientific disciplines as they provide a method for extracting statistical information about large, complicated systems. for some self-assembly models, markov chains can be used to predict both equilibrium and non-equilibrium dynamics. in fact, the efficiency of these self-assembly algorithms can be related to the rate at which simple chains converge to their stationary distribution. we give an overview of the theory of markov chains and show how many natural chains, including some relevant in the context of self-assembly, undergo a phase transition as a parameter representing temperature is varied in the model. we illustrate this behavior for the non-saturated ising model in which there are two types of tiles that prefer to be next to other tiles of the same type. unlike the standard ising model, we also allow empty spaces that are not occupied by either type of tile. we prove that for a local markov chain that allows tiles to attach and detach from the lattice, the rate of convergence is fast at high temperature and slow at low temperature.
characteristics of discrete transfinite time turing machine models: halting times, stabilization times, and normal form theorems. we give an acount of the basic determinants of the courses of computation of the infinite time turing machine model of hamkins and kidder, a model of computation which allows for transfinitely many steps of computation, and therefore may accept and output infinite strings of bits. we provide, inter alia, a normal form theorem, and a characterisation of which ordinals start gaps in halting times of such machines.
strict self-assembly of discrete sierpinski triangles. winfree (1998) showed that discrete sierpinski triangles can self-assemble in the tile assembly model. a striking molecular realization of this self-assembly, using dna tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by rothemund, papadakis, and winfree (2004). precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete sierpinski triangles. this paper addresses the more challenging problem of the strict self-assembly of discrete sierpinski triangles, i.e., the task of tiling a discrete sierpinski triangle and nothing else. we first prove that the standard discrete sierpinski triangle cannot strictly self-assemble in the tile assembly model. we then define the fibered sierpinski triangle, a discrete sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered sierpinski triangle strictly self-assembles in the tile assembly model. in contrast with the simple xor algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations. we verify our strict self-assembly using the local determinism method of soloveichik and winfree (2007).
introducing time in reaction systems. reaction systems are a formal model of interactions between biochemical reactions. the main observation underlying the formulation of this model is that such interactions are based on two basic mechanisms: facilitation and inhibition. this paper continues the investigation of reaction systems, and in particular, it proposes a formal framework for introducing time into reaction systems. within this framework one can formally define and investigate notions such as reaction times, creation times of compounds, their life spans, etc.
combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-euclidean spaces. miller, teng, thurston, and vavasis proved a geometric separator theorem which implies that the k-nearest neighbor graph (k-nng) of every set of n points in r^d has a balanced vertex separator of size o(n^1^-^1^/^dk^1^/^d). spielman and teng then proved that the fiedler value - the second smallest eigenvalue of the laplacian matrix - of the k-nng of any n points in r^d is o((k/n)^2^/^d). in this paper, we extend these two results to nearest neighbor graphs in a metric space with a finite doubling dimension and in a metric space that is nearly-euclidean. we prove that for every l>0, if (x,dist) forms a metric space with doubling dimension @c, then the k-nng of every set p of n points in x has a vertex separator of size o(k^2l(64l+8)^2^@clog^2lslogn+nl), where l and s are, respectively, the maximum and minimum distances between any two points in p. we show how to use the singular value decomposition method to approximate a k-nng in a nearly-euclidean space by a euclidean k-nng. this approximation enables us to obtain an upper bound on the fiedler value of k-nngs in a nearly-euclidean space.
dynamic tcp acknowledgment with sliding window. the dynamic tcp acknowledgement problem which focuses the acknowledgment mechanism in tcp protocol has been intensively studied in the area of competitive analysis. however, its framework does not consider the sliding window in the tcp protocol that restricts the maximum number of packets that the sender can inject into the network without an acknowledgement. this paper proposes a new problem in which the sliding window is realistically integrated. we study how the ability of on-line algorithms changes, depending on whether the receiver is taught the window size. the greater part of this paper assumes that the window size is a constant integer w. we first show that, if w is given, the optimal on-line algorithm for the previous framework can be extended to our new framework and achieves the optimal competitive ratio of 2. next we prove that, if w is not given, the lower bound of the competitive ratio for an algorithm class which contains the optimal algorithm for the previous framework depends on the peak packet rate t from the sender and w, and is not better than (t/w+[t/w]-1)-competitive. then, we prove that there exists an on-line algorithm that is ([t/w]+2)-competitive, when w is unknown. an optimal off-line algorithm is also presented in this paper. significantly, our problem models the situation in which an on-line algorithm involuntarily transforms the input and processes the modified input without noticing the transformation.
the degree distribution of random k-trees. a power law degree distribution is established for a graph evolution model based on the graph class of k-trees. this k-tree-based graph process can be viewed as an idealized model that captures some characteristics of the preferential attachment and copying mechanisms that existing evolving graph processes fail to model due to technical obstacles. the result also serves as a further cautionary note reinforcing the point of view that a power law degree distribution should not be regarded as the only important characteristic of a complex network, as has been previously argued [d. achlioptas, a. clauset, d. kempe, c. moore, on the bias of traceroute sampling, or power-law degree distribution in regular graphs, in: proceedings of the 37th acm symposium on theory of computing, stoc'05, 2005, pp. 694-703; l. li, d. alderson, j. doyle, w. willinger, towards a theory of scale-free graphs: definition, properties, and implications, internet mathematics 2 (4) (2005) 431-523; m. mitzenmacher, the future of power law research, internet mathematics, 2 (4) (2005) 525-534].
effective dimension of points visited by brownian motion. we consider the individual points on a martin-lof random path of brownian motion. we show that (1) khintchine's law of the iterated logarithm holds at almost all points; and (2) there exist points (besides the trivial example of the origin) having effective dimension
regular production systems and triangle tilings. we discuss regular production systems as a tool for analyzing tilings in general. as an application we give necessary and sufficient conditions for a generic triangle to admit a tiling of and show that almost every triangle that admits a tiling is "weakly aperiodic". we pause for informal discussion of a variety of other applications, such as non-quasi-isometric maps between regular tilings, non-periodic archimedean tilings, growth, and decidability. most generally, regular production systems provide a model for the organized growth of surfaces along a front, subject to local rules.
polynomial algorithms for approximating nash equilibria of bimatrix games. we focus on the problem of computing an @e-nash equilibrium of a bimatrix game, when @e is an absolute constant. we present a simple algorithm for computing a 34-nash equilibrium for any bimatrix game in strongly polynomial time and we next show how to extend this algorithm so as to obtain a (potentially stronger) parameterized approximation. namely, we present an algorithm that computes a 2+@l4-nash equilibrium, where @l is the minimum, among all nash equilibria, expected payoff of either player. the suggested algorithm runs in time polynomial in the number of strategies available to the players.
private multiparty sampling and approximation of vector combinations. we consider the problem of private efficient data mining of vertically-partitioned databases. each of several parties holds a column of a data matrix (a vector) and the parties want to investigate the componentwise combination of their vectors. the parties want to minimize communication and local computation while guaranteeing privacy in the sense that no party learns more than necessary. sublinear-communication private protocols have primarily been studied only in the two-party case. in contrast, this work focuses on multi-party settings. first, we give efficient private multiparty protocols for sampling a row of the data matrix and for computing arbitrary functions of a random row, where the row index is additively shared among two or more parties. these results can be used to obtain private approximation protocols for several useful combination functionalities. moreover, these results have some interesting consequences for the general problem of reducing sublinear-communication secure multiparty computation to two-party private information retrieval (pir). second, we give protocols for computing approximations (summaries) of the componentwise sum, minimum, and maximum of the columns. here, while providing a weaker privacy guarantee (where the approximation may leak up to the entire output vector), our protocols are extremely efficient. in particular, the required cryptographic overhead (compared to non-private solutions) is polylogarithmic in the number of rows.