waashk/dblp huggingface dataset:
a note on the number of squares in a word. fraenkel and simpson [a.s. fraenkel, j. simpson, how many squares can a string contain? j. combin. theory ser. a 82 (1998) 112-120] proved that the number of squares in a word of length n is bounded by 2n. in this note we improve this bound to 2n-@q(logn). based on the numerical evidence, the conjectured bound is n.
conjugacy of morphisms and lyndon decomposition of standard sturmian words. using the notions of conjugacy of morphisms and of morphisms preserving lyndon words, we answer a question of g. melancon. we characterize cases where the sequence of lyndon words in the lyndon factorization of a standard sturmian word is morphic. in each possible case, the corresponding morphism is given.
letter frequency in infinite repetition-free words. we estimate the extremal letter frequency in infinite words over a finite alphabet avoiding some repetitions. for ternary square-free words, we improve the bounds of tarannikov on the minimal letter frequency, and prove that the maximal letter frequency is 255653. kolpakov et al. have studied the function @r such that @r(x) is the minimal letter frequency in an infinite binary x-free word. in particular, they have shown that @r is discontinuous at 73 and at every integer at least 3. we answer one of their questions by providing some other points of discontinuity for @r. finally, we propose stronger versions of dejean's conjecture on repetition threshold in which unequal letter frequencies are required.
weighted automata and weighted logics. weighted automata are used to describe quantitative properties in various areas such as probabilistic systems, image compression, speech-to-text processing. the behaviour of such an automaton is a mapping, called a formal power series, assigning to each word a weight in some semiring. we generalize buchi's and elgot's fundamental theorems to this quantitative setting. we introduce a weighted version of mso logic and prove that, for commutative semirings, the behaviours of weighted automata are precisely the formal power series definable with particular sentences of our weighted logic. we also consider weighted first-order logic and show that aperiodic series coincide with the first-order definable ones, if the semiring is locally finite, commutative and has some aperiodicity property.
balanced allocation and dictionaries with tightly packed constant size bins. we study a particular aspect of the balanced allocation paradigm (also known as the ''two-choices paradigm''): constant sized bins, packed as tightly as possible. let d>=1 be fixed, and assume there are m bins of capacity d each. to each of n@?dm balls two possible bins are assigned at random. how close can dm/n=1+@e be to 1 so that with high probability each ball can be put into one of the two bins assigned to it without any bin overflowing? we show that @e>(2/e)^d^-^1 is sufficient. if a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. we show that on average it takes constant time to rearrange the balls to achieve this, for @e>@b^d, for some constant @b=1. keys are assigned to buckets by two fully random hash functions. how many keys can be placed in these bins, if key x may go to bin h"1(x) or to bin h"2(x)? we obtain an implementation of a dictionary that accommodates n keys in m=(1+@e)n/d buckets of size d=o(log(1/@e)), so that key x resides in bucket h"1(x) or h"2(x). for a lookup operation, only two hash functions have to be evaluated and two segments of d contiguous memory cells have to be inspected. if d>=1+3.26@?ln(1/@e), a static arrangement exists with high probability. if d>=16@?ln(1/@e), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/@e)^o^(^l^o^g^l^o^g^(^1^/^@e^)^).
powers in a class of a-strict standard episturmian words. this paper concerns a specific class of strict standard episturmian words whose directive words resemble those of characteristic sturmian words. in particular, we explicitly determine all integer powers occurring in such infinite words, extending recent results of damanik and lenz [d. damanik, d. lenz, powers in sturmian sequences, european j. combin. 24 (2003) 377-390, doi:10.1016/s0195-6698(03)00026-x], who studied powers in sturmian words. the key tools in our analysis are canonical decompositions and a generalization of singular words, which were originally defined for the ubiquitous fibonacci word. our main results are demonstrated via some examples, including the k-bonacci word, a generalization of the fibonacci word to a k-letter alphabet (k>=2).
on the arithmetical complexity of sturmian words. using the geometric dual technique by berstel and pocchiola, we give a uniform o(n^3) upper bound for the arithmetical complexity of a sturmian word. we also give explicit expressions for the arithmetical complexity of sturmian words of slope between 1/3 and 2/3 (in particular, of the fibonacci word). in this case, the difference between the genuine arithmetical complexity function and our upper bound is bounded, and ultimately 2-periodic. in fact, our formula is valid not only for sturmian words but for rotation words from a wider class.
discrete rotations and symbolic dynamics. the aim of this paper is to study local configurations issued from discrete rotations. the algorithm of discrete rotations that we consider is the discretized rotation. it simply consists in the composition of a euclidean rotation with a rounding operation, as studied in [b. nouvel, e. remila, on colorations induced by discrete rotations, in: dgci, in: lncs, vol. 2886, 2003, pp. 174-183; b. nouvel, e. remila, characterization of bijective discretized rotations, in: international workshop on combinatorial images analysis, 10th international conference, iwcia 2004, auckland, new zealand, december 1-4, 2004, in: lncs, vol. 3322, 2004, pp. 248-259; b. nouvel, e. remila, configurations induced by discrete rotations: periodicity and quasiperiodicity properties, discrete appl. math. 2-3 (147) (2005) 325-343]. it is possible to encode all the information concerning a discrete rotation as two multidimensional words c"@a and c"@a^' that we call configurations. in this paper, we introduce two discrete dynamical systems defined by a z^2-action on the two-dimensional torus that allow us to describe the configurations c"@a and c"@a^' via a suitable symbolic coding; we then deduce various combinatorial properties for both families of configurations, and in particular, results concerning densities of symbol occurrence.
tight lower bounds for query processing on streaming and external memory data. it is generally assumed that databases have to reside in external, inexpensive storage because of their sheer size. current technology for external storage systems presents us with a reality that, performance-wise, a small number of sequential scans of the data is strictly preferable over random data accesses. database technology-in particular query processing technology-has developed around a notion of memory hierarchies with layers of greatly varying sizes and access times. it seems that the current technologies scale up to their tasks and are very successful, but on closer investigation it may appear that our theoretical understanding of the problems involved-and of optimal algorithms for these problems-is not quite as developed. recently, data stream processing has become an object of study by the database management community, but from the viewpoint of database theory, this is really a special case of the query processing problem on data in external storage where we are limited to a single scan of the input data. in the present paper we study a clean machine model for external memory and stream processing. we establish tight bounds for the data complexity of core xpath evaluation and filtering. we show that the number of scans of the external data induces a strict hierarchy (as long as internal memory space is sufficiently small, e.g., polylogarithmic in the size of the input). we also show that neither joins nor sorting are feasible if the product of the number r(n) of scans of the external memory and the size s(n) of the internal memory buffers is sufficiently small, i.e., of size o(n).
reversals and palindromes in continued fractions. several results on continued fractions expansions are on indirect consequences of the mirror formula. we survey occurrences of this formula for sturmian real numbers, for (simultaneous) diophantine approximation and for formal power series.
partial words and the critical factorization theorem revisited. in this paper, we consider one of the most fundamental results on the periodicity of words, namely the critical factorization theorem. given a word w and nonempty words u,v satisfying w=uv, the minimal local period associated with the factorization (u,v) is the length of the shortest square at position |u|-1. the critical factorization theorem shows that for any word, there is always a factorization whose minimal local period is equal to the minimal period (or global period) of the word. crochemore and perrin presented a linear time algorithm (in the length of the word) that finds a critical factorization from the computation of the maximal suffixes of the word with respect to two total orderings on words: the lexicographic ordering related to a fixed total ordering on the alphabet, and the lexicographic ordering obtained by reversing the order of letters in the alphabet. here, by refining crochemore and perrin's algorithm, we give a version of the critical factorization theorem for partial words (such sequences may contain "do not know" symbols or "holes"). our proof provides an efficient algorithm which computes a critical factorization when one exists. our results extend those of blanchet-sadri and duncan for partial words with one hole. a world wide web server interface at http://www.uncg.edu/mat/research/cft2/ has been established for automated use of the program.
finding large cliques in sparse semi-random graphs by simple randomized search heuristics. surprisingly, general heuristics often solve some instances of hard combinatorial problems quite sufficiently, although they do not outperform specialized algorithms. here, the behavior of simple randomized optimizers on the maximum clique problem is investigated. we focus on semi-random models for sparse graphs, in which an adversary is even allowed to insert a limited number of edges (and not only to remove them). in the course of these investigations the approximation behavior on general graphs and the optimization behavior for sparse graphs and further semi-random graph models are also considered. with regard to the optimizers, particular interest is given to the influences of the population size and the search operator.
reasoning about probabilistic sequential programs. a complete and decidable hoare-style calculus for iteration-free probabilistic sequential programs is presented using a state logic with truth-functional propositional (not arithmetical) connectives.
the bipanconnectivity and m-panconnectivity of the folded hypercube. the interconnection network considered in this paper is the folded hypercube that is an attractive variance of the well-known hypercube. the folded hypercube is superior to the hypercube in many criteria, such as diameter, connectivity and fault diameter. in this paper, we study the path embedding aspects, bipanconnectivity and m-panconnectivity, of the n-dimensional folded hypercube. a bipartite graph is bipanconnected if each pair of vertices x and y are joined by the bipanconnected paths that include a path of each length s satisfying and is even, where n is the number of vertices, and denotes the shortest distance between x and y. a graph is m-panconnected if each pair of vertices x and y are joined by the paths that include a path of each length ranging from m to n-1. in this paper, we introduce a new graph called the path-of-ladders. by presenting algorithms to embed the path-of-ladders into the folded hypercube, we show that the n-dimensional folded hypercube is bipanconnected for n is an odd number. we also show that the n-dimensional folded hypercube is strictly (n-1)-panconnected for n is an even number. that is, each pair of vertices are joined by the paths that include a path of each length ranging from n-1 to n-1; and the value n-1 reaches the lower bound of the problem.
on approximation algorithms of k-connected m-dominating sets in disk graphs. connected dominating set (cds) has been proposed as the virtual backbone to alleviate the broadcasting storm in wireless ad hoc networks. most recent research has extensively focused on the construction of 1-connected 1-dominating set (1-cds) in homogeneous networks. however, the nodes in the cds need to carry other node's traffic and nodes in wireless networks are subject to failure. therefore, it is desirable to construct a fault tolerant cds. in this paper, we study a general fault tolerant cds problem, called k-connected m-dominating set (k-m-cds), in heterogeneous networks. we first present two approximation algorithms for 1-m-cds and k-k-cds problems. using disk graphs to model heterogeneous networks, we show that our algorithms have a constant approximation ratio. based on these two algorithms, we further develop a general algorithm for k-m-cds. we also provide an interesting analysis for a special case of k-m-cds, where k=m+1.
automata theory based on quantum logic: reversibilities and pushdown automata. automata theory based on quantum logic, called l-valued finite automata (l-vfas), may be viewed as a logical approach to quantum computing. this work is mainly divided into two parts: one part deals with reversibility of l-vfas, and the other establishes a basic framework of l-valued pushdown automata (l-vpdas). first we provide some preliminaries concerning quantum logic and l-vfas, and we prove a useful property of l-valued successor and source operators. then we clarify the relationships between various reversibilities closely related to quantum finite automata in the literature. in particular, we define a reversibility of l-vfas which is termed as retrievability, and we clarify the relationships between a number of different fashions regarding retrievability of l-vfas. we prove that some of them are equivalent, but for the others to be equivalent the truth-value set is required to satisfy a certain condition. this is an essential difference from the classical situation. afterwards, we introduce l-vpdas and show that the class of the languages accepted by l-vpdas by empty stack coincides with that accepted by l-vpdas by final state. finally, we provide some examples of l-vfas and conclude with some remarks.
dual-bounded generating problems: efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data. we show that |x|@?n|y| must hold for two finite sets x,y@?r^n whenever they can be separated by a nonnegative linear function such that x is above y and the componentwise minimum of any two distinct points in x is dominated by some point in y. as a consequence, we obtain an incremental quasi-polynomial time algorithm for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p-inefficient points of a given discrete probability distribution, and for generating all maximal hyper-rectangles which contain a specified fraction of points of a given set in r^n. this provides a substantial improvement over previously known exponential time algorithms for these generation problems related to integer and stochastic programming, and data mining. furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, implying that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.
communication tree problems. in this paper, we deal with the problem of constructing optimal communication trees satisfying given communication requirements. we consider two constant degree tree communication models and several cost measures. first, we analyze whether a tree selected at random provides a good randomized approximation algorithm, and we show that such a construction fails for some of the measures. secondly, we provide approximation algorithms for the case in which the communication requirements are given by a random graph in two different random models, namely the classical g"n","p and random geometric graphs. finally, we conclude with some open problems.
pushdown dimension. resource-bounded dimension is a notion of computational information density of infinite sequences based on computationally bounded gamblers. this paper develops the theory of pushdown dimension and explores its relationship with finite-state dimension. the pushdown dimension of any sequence is trivially bounded above by its finite-state dimension, since a pushdown gambler can simulate any finite-state gambler. we show that for every rational 0
optimal routing in double loop networks. in this paper, we study the problem of finding the shortest path in circulant graphs with an arbitrary number of jumps. we provide algorithms specifically tailored for weighted undirected and directed circulant graphs with two jumps which compute the shortest path. our method only requires o(logn) arithmetic operations and the total bit complexity is o(log^2nloglognlogloglogn), where n is the number of the graph's vertices. this elementary and efficient shortest path algorithm has been derived from the closest vector problem (cvp) of lattices in dimension two and with an @?"1 norm.
algorithms for minimum m-connected k-tuple dominating set problem. in wireless sensor networks, a virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum connected dominating set (cds) problem. in this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. this problem can be formalized as the minimum m-connected k-tuple dominating set problem, which is a general version of minimum cds problem with m=1 and k=1. we propose three centralized algorithms with small approximation ratios for small m and improve the current best results for small k.
every real number greater than 1 is a critical exponent. we prove that for every real number @a>1 there exists an infinite word w over a finite alphabet such that @a is the critical exponent of w.
np-completeness results for some problems on subclasses of bipartite and chordal graphs. extending previous np-completeness results for the harmonious coloring problem and the pair-complete coloring problem on trees, bipartite graphs and cographs, we prove that these problems are also np-complete on connected bipartite permutation graphs. we also study the k-path partition problem and, motivated by a recent work of steiner [g. steiner, on the k-path partition of graphs, theoret. comput. sci. 290 (2003) 2147-2155], where he left the problem open for the class of convex graphs, we prove that the k-path partition problem is np-complete on convex graphs. moreover, we study the complexity of these problems on two well-known subclasses of chordal graphs namely quasi-threshold and threshold graphs. based on the work of bodlaender [h.l. bodlaender, achromatic number is np-complete for cographs and interval graphs, inform. process. lett. 31 (1989) 135-138], we show np-completeness results for the pair-complete coloring and harmonious coloring problems on quasi-threshold graphs. concerning the k-path partition problem, we prove that it is also np-complete on this class of graphs. it is known that both the harmonious coloring problem and the k-path partition problem are polynomially solvable on threshold graphs. we show that the pair-complete coloring problem is also polynomially solvable on threshold graphs by describing a linear-time algorithm.
approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. for a given graph g over n vertices, let opt"g denote the size of an optimal solution in g of a particular minimization problem (e.g., the size of a minimum vertex cover). a randomized algorithm will be called an @a-approximation algorithm with an additive error for this minimization problem if for any given additive error parameter @e>0 it computes a value opt@? such that, with probability at least 2/3, it holds that opt"g@?opt@?@?@a@?opt"g+@en. assume that the maximum degree or average degree of g is bounded. in this case, we show a reduction from local distributed approximation algorithms for the vertex cover problem to sublinear approximation algorithms for this problem. this reduction can be modified easily and applied to other optimization problems that have local distributed approximation algorithms, such as the dominating set problem. we also show that for the minimum vertex cover problem, the query complexity of such approximation algorithms must grow at least linearly with the average degree d@? of the graph. this lower bound holds for every multiplicative factor @a and small constant @e as long as d@?=o(n/@a). in particular this means that for dense graphs it is not possible to design an algorithm whose complexity is o(n).
polylogarithmic-round interactive proofs for conp collapse the exponential hierarchy. if every language in conp has a constant-round interactive proof system, then the polynomial-time hierarchy collapses [r.b. boppana, j. håstad, s. zachos, does co-np have short interactive proofs? information processing letters 25 (2) (1987) 127-132]. on the other hand, the well-known lfkn protocol gives o(n)-round interactive proof systems for all languages in conp [c. lund, l. fortnow, h. karloff, n. nisan, algebraic methods for interactive proof systems, journal of the association for computing machinery 39 (4) (1992) 859-868]. we consider the question of whether it is possible for conp to have interactive proof systems with polylogarithmic-round complexity. we show that this is unlikely by proving that if a conp-complete set has a polylogarithmic-round interactive proof system, then the exponential-time hierarchy collapses. we also consider exponential versions of the karp-lipton theorem and yap's theorem.
block lu factors of generalized companion matrix pencils. we present formulas for computations involving companion matrix pencils as may arise in considering polynomial eigenvalue problems. in particular, we provide explicit companion matrix pencils for matrix polynomials expressed in a variety of polynomial bases including monomial, orthogonal, newton, lagrange, and bernstein/bezier bases. additionally, we give a pair of explicit lu factors associated with each pencil and a prescription for block pivoting when required.