waashk/dblp huggingface dataset:
fully asynchronous behavior of double-quiescent elementary cellular automata. in this paper we propose a probabilistic analysis of the fully asynchronous behavior (i.e., two cells are never simultaneously updated, as in a continuous time process) of elementary finite cellular automata (i.e., {0, 1} states, radius 1 and unidimensional) for which both states are quiescent (i.e., (0, 0, 0) ↦ 0 and (1, 1, 1) ↦ 1). it has been experimentally shown in previous works that introducing asynchronism in the global function of a cellular automata was perturbing its behavior, but as far as we know, only few theoretical work exists on the subject. the cellular automata we consider live on a ring of size n and asynchronism is introduced as follows: at each time step one cell is selected uniformly at random and the transition is made on this cell while the others stay in the same state. among the 64 cellular automata belonging to the class we consider, we show that 9 of them diverge on all non-trivial configurations while the 55 other converge almost surely to a random fixed point. we show that the exact convergence time of these 55 automata can only take the following values: either 0, θ(n ln n), θ(n2), θ(n3 ) or θ(n2n). furthermore, the global behavior of each of these cellular automata is fully determined by reading its code.
an algebraic characterization of the set of succession rules. in this paper we will give a formal description of succession rules in terms of linear operators satisfying certain conditions. this representation allows us to introduce a system of well-defined operations into the set of succession rules and then to tackle problems of combinatorial enumeration simply by using operators instead of generating functions. finally, we will suggest several open problems whose solution should lead to an algebraic characterization of the set of succession rules.
neighborhood unions and regularity in graphs. one way to generalize the concept of degree in a graph is to consider the neighborhood n(s) of an independent set s instead of a simple vertex. the minimum generalized degree of order t of g is then defined, for 1&le;t&le;&agr; (the independence number of g), by ut=min{|n(s)|: s (semi-circle right) v; s is independent and |s| = t}. the graph g is said to be u(sub)t-regular if |n(s1)| = |n(s2)| for every pair s1; s2 of independent sets of t elements, totally u(sub)t-regular (resp. totally u(sub)t&le;s-regular where s is given &le;&agr;) if it is u(sub)t-regular for every t&le;&agr; (resp. for every t&le;s), strongly u(sub)t-regular (resp. strongly u(sub)t6s-regular) if |n(s1)| = |n(s2)| for every pair s1; s2 of independent sets of g (resp. every pair of independent sets of order at most s). we determine the strongly u(sub)t&le;2-regular graphs and give some properties of the totally u(sub)t&le;2-regular and totally u(sub)t-regular graphs. some of our results improve already known results.
list matrix partitions of chordal graphs. it is well known that a clique with k + 1 vertices is the only minimal obstruction to k-colourability of chordal graphs. a similar result is known for the existence of a cover by l cliques. both of these problems are in fact partition problems, restricted to chordal graphs. the first seeks partitions into k independent sets, and the second is equivalent to finding partitions into l cliques. in an earlier paper we proved that a chordal graph can be partitioned into k independent sets and l cliques if and only if it does not contain an induced disjoint union of l + 1 cliques of size k + 1. (a linear time algorithm for finding such partitions can be derived from the proof.)in this paper we expand our focus and consider more general partitions of chordal graphs. for each symmetric matrix m over 0, 1, *, the m-partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with certain pairs of sets being required to have no edges, or to have all edges joining them, as encoded in the matrix m. moreover, the vertices of the input chordal graph can be equipped with lists, restricting the parts to which a vertex can be placed. such (list) partitions generalize (list) colourings and (list) homomorphisms, and arise frequently in the theory of graph perfection. we show that many m-partition problems that are np-complete in general become solvable in polynomial time for chordal graphs, even in the presence of lists. on the other hand, we show that there are m-partition problems (without lists) that remain np-complete for chordal graphs. it is not known whether or not each list m-partition problem is np-complete or polynomial, but it has been shown that each is np-complete or quasi-polynomial (no(log n)). for chordal graphs even this 'quasi-dichotomy' is not known, but we do identify large families of matrices m for which dichotomy, or at least quasi-dichotomy, holds.we also discuss forbidden subgraph characterizations of graphs admitting an m-partition. such characterizations have recently been investigated for partitions of perfect graphs, and we focus on highlighting the improvements one can obtain for the class of chordal, rather than just perfect, graphs.
combining request scheduling with web caching. we extend the classic paging model by allowing reordering of requests under the constraint that a request is delayed by no longer than a predetermined number of time steps. we first give a dynamic programming algorithm to solve the offline case. then we give tight bounds on competitive ratios for the online case. for caches of size k, we obtain bounds of k + o(1) for deterministic algorithms and θ(log k) for randomized algorithms. we also give bounds for the case where either the online or the offline algorithm can reorder the requests, but not both. finally, we extend our analysis to the case where pages have different sizes.
dichotomies for classes of homomorphism problems involving unary functions. we study non-uniform constraint satisfaction problems where the underlying signature contains constant and function symbols as well as relation symbols. amongst our results are the following. we establish a dichotomy result for the class of non-uniform constraint satisfaction problems over the signature consisting of one unary function symbol by showing that every such problem is either complete for l, via very restricted logical reductions, or trivial (depending upon whether the template function has a fixed point or not). we show that the class of non-uniform constraint satisfaction problems whose templates are structures over the signature λ2 consisting of two unary function symbols reflects the full computational significance of the class of non-uniform constraint satisfaction problems over relational structures. we prove a dichotomy result for the class of non-uniform constraint satisfaction problems where the template is a λ2-structure with the property that the two unary functions involved are the reverse of one another, in that every such problem is either solvable in polynomial-time or np-complete. finally, we extend some of our results to the situation where instances of non-uniform constraint satisfaction problems come equipped with lists of elements of the template structure which restrict the set of allowable homomorphisms.
on three variants of rewriting p systems. we continue here the study of p systems with string objects processed by rewriting rules, by investigating some questions which are classic in formal language theory: leftmost derivation, conditional use of rules (permitting and forbidding conditions), relationships with language families in chomsky and lindenmayer hierarchies.
schedulability analysis of fixed-priority systems using timed automata. in classic scheduling theory, real-time tasks are usually assumed to be periodic, i.e. tasks are released and computed with fixed rates periodically. to relax the stringent constraints on task arrival times, we propose to use timed automata to describe task arrival patterns. in a previous work, it is shown that the general schedulability checking problem for such models is a reachability problem for a decidable class of timed automata extended with subtraction. unfortunately, the number of clocks needed in the analysis is proportional to the maximal number of schedulable task instances associated with a model, which is in many cases huge. in this paper, we show that for fixed-priority scheduling strategy, the schedulability checking problem can be solved using standard timed automata with two extra clocks in addition to the clocks used in the original model to describe task arrival times. the analysis can be done in a similar manner to response time analysis in classic rate-monotonic analysis (rma). the result is further extended to systems with data-dependent control, in which the release time of a task may depend on the time-point at which other tasks finish their execution. for the case when the execution times of tasks are constants, we show that the schedulability problem can be solved using n + 1 extra clocks, where n is the number of tasks. the presented analysis techniques have been implemented in the times tool. for systems with only periodic tasks, the performance of the tool is comparable with tools implementing the classic rma technique based on equation-solving, without suffering from the exponential explosion in the number of tasks.
on the drift of short schedules. for the job shop scheduling problem, the drift of a schedule is the maximum difference between the number of operations performed by two jobs within a time interval. we show instances of the problem for which every short schedule must allow for nonconstant drift.
an enhanced property of factorizing codes. the investigation of the factorizing codes c, i.e., codes satisfying schützenberger's factorization conjecture, has been carried out from different viewpoints, one of them being the description of structural properties of the words in c. in this framework, we can now improve an already published result. more precisely, given a factorizing code c over a two-letter alphabet a = {a, b}, it was proved by de felice that the words in the set c1 = c ∩ a*ba* could be arranged over a matrix related to special factorizations of the cyclic groups. we now prove that, in addition, these matrices can be recursively constructed starting with those corresponding to prefix/suffix codes.
computation in a distributed information market. according to economic theory--supported by empirical and laboratory evidence--the equilibrium price of a financial security reflects all of the information regarding the security's value. we investigate the computational process on the path toward equilibrium, where information distributed among traders is revealed step-by-step over time and incorporated into the market price. we develop a simplified model of an information market, along with trading strategies, in order to formalize the computational properties of the process. we show that securities whose payoffs cannot be expressed as weighted threshold functions of distributed input bits are not guaranteed to converge to the proper equilibrium predicted by economic theory. on the other hand, securities whose payoffs are threshold functions are guaranteed to converge, for all prior probability distributions. moreover, these threshold securities converge in at most n rounds, where n is the number of bits of distributed information. we also prove a lower bound, showing a type of threshold security that requires at least n/2 rounds to converge in the worst case.
is dna computing viable for 3-sat problems? adleman reported how to solve a 7-vertex instance of the hamiltonlan path problem by means of dna manipulations. after that a major goal of subsequent research is how to use dna manipulations to solve np-hard problems, especially 3-sat problems. lipton proposed dna experiments on test tubes to solve 3-sat problems. liu et al. reported how to solve a simple case of 3-sat using dna computing on surfaces. lipton's model of dna computing is simple and intuitive for 3-sat problems. the separate (or extract) operation, which is a key manipulation of dna computing, only extracts some of the required dna strands and lipton thinks that a typical percentage might be 90. but it is unknown what would happen due to imperfect extract operation. let p be the rate, where 0 < p < 1. assume that for each distinct string s in a test tube, there are 10l (l=13 proposed by adleman) copies of s and that extracting each of the required dna strands is equally likely. here, the present paper will report, no matter how large l is and no matter how close to 1 p is, there always exists a class of 3-sat problems such that dna computing error must occur. therefore, dna computing is not viable for 3-sat.
on graph problems in a semi-streaming model. we formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. in this model, the input graph, g = (v, e), is presented as a stream of edges (in adversarial order), and the storage space of an algorithm is bounded by o(n ċ polylog n), where n = |v|. we are particularly interested in algorithms that use only one pass over the input, but, for problems where this is provably insufficient, we also look at algorithms using constant or, in some cases, logarithmically many passes. in the course of this general study, we give semi-streaming constant approximation algorithms for the unweighted and weighted matching problems, along with a further algorithmic improvement for the bipartite case. we also exhibit log n/log log n semi-streaming approximations to the diameter and the problem of computing the distance between specified vertices in a weighted graph. these are complemented by ω(log(1-ε) n) lower bounds.
generating well-shaped d-dimensional delaunay meshes. a d-dimensional simplicial mesh is a delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. a mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. it is a long-term open problem to generate well-shaped d-dimensional delaunay meshes for a given polyhedral domain. in this paper, we present a refinement-based method that generates well-shaped d-dimensional delaunay meshes for any plc domain with no small input angles. furthermore, we show that the generated well-shaped mesh has o(n) d-simplices, where n is the smallest number of d-simplices of any almost-good meshes for the same domain. here a mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.
traveling salesmen in the presence of competition. we propose the "competing salesmen problem" (csp), a two-player competitive version of the classical traveling salesman problem. this problem arises when considering two competing salesmen instead of just one. the concern for a shortest tour is replaced by the necessity to reach any of the customers before the opponent does.in particular, we consider the situation where players take turns, moving along one edge at a time within a graph g = (v,e). the set of customers is given by a subset vc ⊆ v of the vertices. at any given time, both players know of their opponent's position. a player wins if he is able to reach a majority of the vertices in vc before the opponent does.we prove that the csp is pspace-complete, even if the graph is bipartite, and both players start at distance 2 from each other. furthermore, we show that the starting player may not be able to avoid losing the game, even if both players start from the same vertex. however, for the case of bipartite graphs, we show that the starting player always can avoid a loss. on the other hand, we show that the second player can avoid to lose by more than one customer, when play takes place on a graph that is a tree t, and vc consists of leaves of t. it is unclear whether a polynomial strategy exists for any of the two players to force this outcome. for the case where t is a star (i.e., a tree with only one vertex of degree higher than two) and vc consists of n leaves of t, we give a simple and fast strategy which is optimal for both players. if vc consists not only of leaves, we point out that the situation is more involved.
on-line single-server dial-a-ride problems. in this paper results on the dial-a-ride problem with a single server are presented. requests for rides consist of two points in a metric space, a source and a destination. a ride has to be made by the server from the source to the destination. the server travels at unit speed in the metric space and the objective is to minimize some function of the delivery times at the destinations. we study this problem in the natural on-line setting. calls for rides come in while the server is traveling. this models, e.g. the taxi problem, or, if the server has capacity more than a minibus or courier service problem. for the version of this problem in which the server has infinite capacity having as objective minimization of the time the last destination is served, we design an algorithm that has competitive ratio 2. we also show that this is best possible, since no algorithm can have competitive ratio better than 2 independent of the capacity of the server. besides, we give a simple 2.5-competitive algorithm for the case with finite capacity. then we study the on-line problem with objective minimization of the sum of completion times of the rides. we prove a lower bound on the competitive ration of any algorithm of 1 + 2 for a server with any capacity and of 3 for a server has infinite capacity and the metric space is the real line. the algorithm has competitive ration 15. copyright 2001 elsevier science b.v.
on distance constrained labeling of disk graphs. a disk graph is the intersection graph of a set of disks in the plane. for a k-tuple (p1 ..... pk) of positive integers, a distance constrained labeling of a graph g is an assignment of labels to the vertices of g such that the labels of any pair of vertices at graph distance i in g differ by at least pi, for i = 1,...,k. in the case when k = 1 and p1 = 1, this gives a traditional coloring of g. we propose and analyze several online and offiine labeling algorithms for the class of disk graphs.
a complete complexity classification of the role assignment problem. in social network theory a society is often represented by a simple graph g, where vertices stand for individuals and edges represent relationships between those individuals. the description of the social network is tried to be simplified by assigning roles to the individuals, such that the neighborhood relation is preserved. formally, for a fixed graph r we ask for a vertex mapping r: vg → vr, such that r(ng(u)) = nr(r(u)) for all u ∈ vg.if such a mapping exists the graph g is called r-role assignable and the corresponding decision problem is called the r-role assignment problem. kristiansen and telle conjectured that the r-role assignment problem is an np-complete problem for any simple connected graph r on at least three vertices. in this paper we prove their conjecture. in addition, we determine the computational complexity of the role assignment problem for nonsimple and disconnected role graphs, as these are considered in social network theory as well.
word assembly through minimal forbidden words. we give a linear-time algorithm to reconstruct a finite word w over a finite alphabet a of constant size starting from a finite set of factors of w verifying a suitable hypothesis. we use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. this improves a previous algorithm which worked under the assumption of stronger hypothesis.
compact factors of countable state markov shifts. we study continuous shift commuting maps from transitive countable state markov shifts into compact subshifts. the closure of the image is a coded system. on the other hand, any coded system is the surjective image of some transitive markov shift, which may be chosen locally compact by construction. these two results yield a formal analogy to "the transitive sofic systems are the subshift factors of transitive shifts of finite type". then we consider factor maps which have bounded coding length in some graph presentation (label maps). now the image has to be synchronized, but not every synchronized system can be obtained in this way. we show various restrictions for a surjective label map to exis
polymorphic lambda calculus and subtyping. we present a denotational model for f, the extension of second-order lambda calculus with subtyping defined in cardelli and wegner (acm comput. surveys 17(4) (1985) 471-522.) types are interpreted as arbitrary cpos and elements of types as natural transformations. we prove the soundness of our model with respect to the equational theory of f (cardelli et al. (internat. conf. on theoretical aspects of computer software, lecture notes in computer science, vol. 526, springer, berlin, 1991, pp. 750-770)) and show coherence. our model is of independent interest, because it integrates ad hoc and parametric polymorphism in an elegant fashion, admits nontrivial records and record update operations, and formalizes an "order faithfulness" criterion for well-behaved multiple subtyping.
analysis of randomized load distribution for reproduction trees in linear arrays and rings. high performance computing requires high quality load distribution of processes of a parallel application over processors in a parallel computer at runtime such that both maximum load and dilation are minimized. the performance of a simple randomized load distribution algorithm that dynamically supports tree-structured parallel computations on two simple static networks, namely, linear arrays and rings, is analyzed in this paper. the algorithm spreads newly created tree nodes to neighboring processors, which actually provides randomized dilation-1 tree embedding in a static network. we develop linear systems of equations that characterize expected loads on all processors, and find their closed form solutions under the reproduction tree model, which can generate trees of arbitrary size and shape. the main contribution of the paper is to show that the above simple randomized algorithm is able to generate high-quality dynamic tree embeddings even in very simple and sparse networks such as linear arrays, and rings. in particular, we prove that as tree size becomes large, the asymptotic performance ratio of such a randomized dilation-1 tree embedding is n/(n-1) in linear arrays and is optimal in rings.
decompositions for the edge colouring of reduced indifference graphs. the chromatic index problem--finding the minimum number of colours required for colouring the edges of a graph--is still unsolved for indifference graphs, whose vertices can be linearly ordered so that the vertices contained in the same maximal clique are consecutive in this order. we present new positive evidence for the conjecture: every non neighbourhood-overfull indifference graph can be edge coloured with maximum degree colours. two adjacent vertices are twins if they belong to the same maximal cliques. a graph is reduced if it contains no pair of twin vertices. a graph is overfull if the total number of edges is greater than the product of the maximum degree by ⌈n/2⌉, where n is the number of vertices. we give a structural characterization for neighbourhood-overfull indifference graphs proving that a reduced indifference graph cannot be neighbourhood-overfull. we show that the chromatic index for all reduced indifference graphs is the maximum degree. we present two decomposition methods for edge colouring reduced indifference graphs with maximum degree colours.