waashk/dblp huggingface dataset:
the continuous skolem-pisot problem. we study decidability and complexity questions related to a continuous analogue of the skolem-pisot problem concerning the zeros and nonnegativity of a linear recurrent sequence. in particular, we show that the continuous version of the nonnegativity problem is np-hard in general and we show that the presence of a zero is decidable for several subcases, including instances of depth two or less, although the decidability in general is left open. the problems may also be stated as reachability problems related to real zeros of exponential polynomials or solutions to initial value problems of linear differential equations, which are interesting problems in their own right.
analysis of a cellular automaton model for car traffic with a slow-to-stop rule. we propose a modification of the widely known benjamin-johnson-hui (bjh) cellular automaton model for single-lane traffic simulation. in particular, our model includes a 'slow-to-stop' rule that exhibits more realistic microscopic driver behaviour than the bjh model. we present some statistics related to fuel economy and pollution generation and show that our model differs greatly in these measures. we give concise results based on extensive simulations using our system.
a note on the complexity of c-words. let @c(n) be the number of c^~-words of length n. say that a c^~-word w is left doubly extendable (lde) if both 1w and 2w are c^~. we show that for any positive real number @f and positive integer n such that the proportion of 2's is greater than 12-@f in each lde word of length exceeding n, there are positive constants c"1 and c"2 such that c"1n^l^o^g^3^l^o^g^(^(^3^/^2^)^+^@f^+^(^2^/^n^)^)
enumeration of the perfect sequences of a chordal graph. a graph is chordal if and only if it has no chordless cycle of length more than three. the set of maximal cliques in a chordal graph admits special tree structures called clique trees. a perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. this paper addresses the problem of enumerating all the perfect sequences. although this problem has statistical applications, no efficient algorithm has been proposed. there are two difficulties with developing this type of algorithm. first, a chordal graph does not generally have a unique clique tree. second, a perfect sequence can normally be generated by two or more distinct clique trees. thus it is hard using a straightforward algorithm to generate perfect sequences from each possible clique tree. in this paper, we propose a method to enumerate perfect sequences without constructing clique trees. as a result, we have developed the first polynomial delay algorithm for dealing with this problem. in particular, the time complexity of the algorithm on average is o(1) for each perfect sequence.
recognition of directed acyclic graphs by spanning tree automata. in this paper, we study tree automata for directed acyclic graphs (dags). we define the movement of a tree automaton on a dag so that a dag is accepted by a tree automaton if and only if the dag has a spanning tree accepted by the tree automaton. we call this automaton a spanning tree automaton. the np-completeness of the membership problem of dags for spanning tree automata is shown. however, if inputs are restricted to series-parallel graphs or generalized series-parallel graphs, it is shown that the membership problem for spanning tree automata is solvable in linear time.
parametric random generation of deterministic tree automata. uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. we present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. we also propose an original parametric random generation algorithm to produce sequential letter-to-letter transducers with a fixed number of transitions. we tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top-down tree automata. we apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top-down tree automata construction we also implemented.
embedding of tori and grids into twisted cubes. the hypercube is one of the most popular interconnection networks since it has a simple structure and is easy to implement. an n-dimensional twisted cube, tq"n, is an important variation of hypercube q"n and preserves many of its desirable properties. the problem of how to embed a family of disjoint meshes (or tori) into a host graph has attracted great attention in recent years. however, there is no systematic method proposed to generate the desired meshes and tori in tq"n. in this paper, we develop two systematic linear time algorithms for embedding disjoint multi-dimensional tori into tq"n, n>=7, as follows: (1) for a positive integer m with @?n2@?@?m@?n-4, a family of 2^m disjoint k-dimensional tori of size 2^s^"^1x2^s^"^2x...x2^s^"^k each can be embedded with unit dilation, where k>=2 and @?"i"="1^ks"i@?n-m, and (2) for a positive integer m with 2@?m@?n-5, a family of 2^m disjoint k-dimensional tori of size 2^s^"^1x2^s^"^2x...x2^s^"^k each can be embedded with unit dilation, where k>=2, s"i>=2, @?"i"="1^ks"i@?n-m, and max"1"@?"i"@?"k{s"i}>=n-2m. moreover, we also provide similar embedding results for meshes and hypercubes. our results mean that a family of torus-structured (mesh-structured, or hypercube-structured) parallel algorithms can be executed on the same twisted cube efficiently and in parallel.
improved upper bounds for vertex cover. this paper presents an o(1.2738^k+kn)-time polynomial-space algorithm for vertex cover improving the previous o(1.286^k+kn)-time polynomial-space upper bound by chen, kanj, and jia. most of the previous algorithms rely on exhaustive case-by-case branching rules, and an underlying conservative worst-case-scenario assumption. the contribution of the paper lies in the simplicity, uniformity, and obliviousness of the algorithm presented. several new techniques, as well as generalizations of previous techniques, are introduced including: general folding, struction, tuples, and local amortized analysis. the algorithm also improves the o(1.2745^kk^4+kn)-time exponential-space upper bound for the problem by chandran and grandoni.
preemptive scheduling with simple linear deterioration on a single machine. in this paper we study the problem of scheduling n deteriorating jobs with release dates on a single machine. the processing time of a job is assumed to be the product of its deteriorating rate and its starting time. precedence relations may be imposed on the set of jobs. unlike the classical time-dependent scheduling problems, we assume that the execution of a job can be preempted in the sense that the job's deteriorating rate is reduced when it is preempted and each continuously processed part of a job can be regarded as an independent job with a specified deteriorating rate. the objective is to minimize some common regular scheduling performance measures. we first show that minimizing a class of regular symmetric functions is polynomially solvable. then we construct an o(n^2) algorithm for minimizing the maximum job completion cost with or without precedence constraints. finally we show that minimizing the total weighted completion time is np-hard even if there are only two distinct release dates.
fixed point guided abstraction refinement for alternating automata. in this paper, we develop and evaluate two new algorithms for checking emptiness of alternating automata. these algorithms build on previous works. first, they rely on antichains to efficiently manipulate the state-spaces underlying the analysis of alternating automata. second, they are abstract algorithms with built-in refinement operators based on techniques that exploit information computed by abstract fixed points (and not counter-examples as it is usually the case). the efficiency of our new algorithms is illustrated by experimental results.
growth rates of complexity of power-free languages. we present a new fast algorithm for calculating the growth rate of complexity for regular languages. using this algorithm we develop a space and time efficient method to approximate growth rates of complexity of arbitrary power-free languages over finite alphabets. through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds and discover some general regularities.
the picker-chooser diameter game. positional games are played under several rules on the same hypergraph. we consider some intriguing connections among the outcomes of the maker-breaker and the picker-chooser versions. the latter one was introduced by beck (2002) [5] and proved to be important in understanding positional games in general. beck had the profound conjecture that playing on the same hypergraph, picker has better chances than maker. the main goal of this paper is to confirm this conjecture for the notoriously hard diameter-2 game that was studied by balogh et al. (2009) [1]. the diameter-2 game is also an example of the fact that the probabilistic intuition, or ''erdos paradigm'' can fail completely, however, the acceleration of the game can restore it. the picker-chooser version is closer to erdos paradigm: there are almost matching lower and upper bounds for the critical density. pursuing these goals, we extend the theory of picker-chooser games to biased and discrepancy games, and develop erdos-selfridge type results.
amount of nonconstructivity in deterministic finite automata. when d. hilbert used nonconstructive methods in his famous paper on invariants (1888), p. gordan tried to prevent the publication of this paper considering these methods as non-mathematical. l.e.j. brouwer in the early twentieth century initiated intuitionist movement in mathematics. his slogan was ''nonconstructive arguments have no value for mathematics''. however, p. erdos got many exciting results in discrete mathematics by nonconstructive methods. it is widely believed that these results either cannot be proved by constructive methods or the proofs would have been prohibitively complicated. the author (freivalds, 2008) [10] showed that nonconstructive methods in coding theory are related to the notion of kolmogorov complexity. we study the problem of the quantitative characterization of the amount of nonconstructiveness in nonconstructive arguments. we limit ourselves to computation by deterministic finite automata. the notion of nonconstructive computation by finite automata is introduced. upper and lower bounds of nonconstructivity are proved.
csp duality and trees of bounded pathwidth. we study non-uniform constraint satisfaction problems definable in monadic datalog stratified by the use of non-linearity. we show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. for this, we introduce a new parameter for trees that closely approximates pathwidth and can be characterised via a hypergraph searching game.
playing the perfect kriegspiel endgame. retrograde analysis is an algorithmic technique for reconstructing a game tree starting from its leaves; it is useful to solve some specific subsets of a complex game, for example a chess endgame, achieving optimal play in these situations. position values can then be stored in ''tablebases'' for instant access, in order to save analysis time, as is the norm in professional chess programs. this paper shows that a similar approach can be used to solve subsets of certain imperfect information games such as kriegspiel (invisible chess) endgames. using a brute force retrograde analysis algorithm, a suitable data representation and a special lookup algorithm, one can achieve perfect play, with perfection meaning fastest checkmate in the worst case and without making any assumptions on the opponent. we investigate some kriegspiel endgames (krk, kqk, kbbk and kbnk), building the corresponding tablebases and casting light on some long standing open problems.
taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring. one of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. the robots operate in look-compute-move cycles; in one cycle, a robot takes a snapshot of the current configuration (look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (compute), and in the latter case makes an instantaneous move to this neighbor (move). cycles are performed asynchronously for each robot. in such a restricted scenario, we study the influence of symmetries of the robot configuration on the feasibility of certain computational tasks. more precisely, we deal with the problem of gathering all robots at one node of the graph, and propose a solution based on a symmetry-preserving strategy. when the considered graph is an undirected ring and the number of robots is sufficiently large (more than 18), such an approach is proved to solve the problem for all starting situations, as long as gathering is feasible. in this way we also close the open problem of characterizing symmetric situations on the ring which admit a gathering [r. klasing, e. markou, a. pelc: gathering asynchronous oblivious mobile robots in a ring, theoret. comput. sci. 390 (1) (2008) 27-39]. the proposed symmetry-preserving approach, which is complementary to symmetry-breaking techniques found in related work, appears to be new and may have further applications in robot-based computing.
class constrained bin packing revisited. we study the following variant of the bin packing problem. we are given a set of items, where each item has a (non-negative) size and a color. we are also given an integer parameter k, and the goal is to partition the items into a minimum number of subsets such that for each subset s in the solution, the total size of the items in s is at most 1 (as in the classical bin packing problem) and the total number of colors of the items in s is at most k (which distinguishes our problem from the classical version). we follow earlier work on this problem and study the problem in both offline and online scenarios.
optimality of some algorithms to detect quasiperiodicities. improving a 1993 algorithm of apostolico and ehrenfeucht, independently iliopoulos and mouchard in 1999 and brodal and pedersen in 2000 provided o(nlog(n)) algorithms to determine all maximal quasiperiodicities of a word of length n. we show here the optimality of this bound providing an infinite family of words w containing o(|w|log|w|) maximal quasiperiodicities. we also show that this bound is not reached for the celebrated family of fibonacci words.
parallel-machine scheduling with deteriorating jobs and rejection. we consider several parallel-machine scheduling problems in which the processing time of a job is a (simple) linear increasing function of its starting time and jobs can be rejected by paying penalties. the objective is to minimize the scheduling cost of the accepted jobs plus the total penalty of the rejected jobs. three variations of the scheduling cost are considered in this paper. the first is the makespan, the second is the total weighted completion time (for simple linear deterioration), and the third is the total completion time. for the former two problems, we propose two fully polynomial-time approximation schemes to solve them when the number of machines is fixed. for the last problem, we present an optimal o(n^2)-time dynamic programming algorithm when the deteriorating rates are equal for all jobs.
verifying parallel programs with dynamic communication structures. we address the verification problem of networks of communicating pushdown systems modeling communicating parallel programs with procedure calls. processes in such networks can read the control state of the other processes according to a given communication structure (specifying the observability rights between processes). the reachability problem of such models is undecidable in general. first, we define a class of networks that effectively preserves recognizability (hence, its reachability problem is decidable). then, we consider networks where the communication structure can change dynamically during the execution according to a phase graph. the reachability problem for these dynamic networks being undecidable in general, we define a subclass for which it becomes decidable. then, we consider reachability when the switches in the communication structures are bounded. we show that this problem is undecidable even for one switch. we define a natural class of models for which this problem is decidable. this class can be used in the definition of an efficient semi-decision procedure for the analysis of the general model of dynamic networks. our techniques allowed to find bugs in two versions of a windows nt bluetooth driver.
a combinatorial approach to the analysis of bucket recursive trees. in this work we provide a combinatorial analysis of bucket recursive trees, which have been introduced previously as a natural generalization of the growth model of recursive trees. our analysis is based on the description of bucket recursive trees as a special instance of the so-called bucket increasing trees, which is a family of combinatorial objects introduced in this paper. using this combinatorial description we obtain exact and limiting distribution results for the parameter depth of a specified element, descendants of a specified element and degree of a specified element.
treewidth and minimum fill-in on permutation graphs in linear time. permutation graphs form a well-studied subclass of cocomparability graphs. permutation graphs are the cocomparability graphs whose complements are also cocomparability graphs. a triangulation of a graph g is a graph h that is obtained by adding edges to g to make it chordal. if no triangulation of g is a proper subgraph of h then h is called a minimal triangulation. the main theoretical result of the paper is a characterisation of the minimal triangulations of a permutation graph, that also leads to a succinct and linear-time computable representation of the set of minimal triangulations. we apply this representation to devise linear-time algorithms for various minimal triangulation problems on permutation graphs, in particular, we give linear-time algorithms for computing treewidth and minimum fill-in on permutation graphs.
sharp thresholds for hamiltonicity in random intersection graphs. random intersection graphs, g"n","m","p, is a class of random graphs introduced in karonski (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. each element of the universal sets is chosen independently by some vertex with probability p. two vertices are joined by an edge iff their chosen element sets intersect. given n, m so that m=@?n^@a@?, for any real @a different than one, we establish here, for the first time, a sharp threshold for the graph property ''contains a hamilton cycle''. our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model.
on the number of episturmian palindromes. episturmian words are a suitable generalization to arbitrary alphabets of sturmian words. in this paper we are interested in the problem of enumerating the palindromes in all episturmian words over a k-letter alphabet a"k. we give a formula for the map g"k giving for any n the number of all palindromes of length n in all episturmian words over a"k. this formula extends to k>2 a similar result obtained for k=2 by the second and third authors in 2006. the map g"k is expressed in terms of the map p"k counting for each n the palindromic prefixes of all standard episturmian words (epicentral words). for any n>=0, p"2(n)=@f(n+2), where @f is the totient euler function. the map p"k plays an essential role also in the enumeration formula for the map @l"k counting for each n the finite episturmian words over a"k. similarly to euler's function, the behavior of p"k is quite irregular. the first values of p"k and of the related maps g"k, and @l"k for 3@?k@?6 have been calculated and reported in the paper. some properties of p"k are shown. in particular, broad upper and lower bounds for p"k, as well as for @?"m"="0^np"k(m) and g"k, are determined. finally, some conjectures concerning the map p"k are formulated.
deadline scheduling and power management for speed bounded processors. in this paper we consider online deadline scheduling on a processor that can manage its energy usage by scaling the speed dynamically or entering a sleep state. a new online scheduling algorithm called soa is presented. assuming speed can be scaled arbitrarily high (the infinite speed model), soa can complete all jobs with reduced energy usage, improving the competitive ratio for energy from 2^2^@a^-^2@a^@a+2^@a^-^1+2 (irani et al. (2007) [17]) to @a^@a+2, where @a is the constant involved in the speed-to-power function, commonly believed to be 2 or 3. more importantly, soa is the first algorithm that works well even if the processor has a fixed maximum speed and the system is overloaded. in this case, soa is 4-competitive for throughput and (@a^@a+@a^24^@a+2)-competitive for energy. note that the throughput ratio cannot be better than 4 even if energy is not a concern.
adaptive star grammars and their languages. motivated by applications that require mechanisms for describing the structure of object-oriented programs, adaptive star grammars are introduced, and their fundamental properties are studied. in adaptive star grammars, rules are actually schemata which, via the cloning of so-called multiple nodes, may adapt to potentially infinitely many contexts when they are applied. this mechanism makes adaptive star grammars more powerful than context-free graph grammars. nevertheless, they turn out to be restricted enough to share some of the basic characteristics of context-free devices. in particular, the underlying substitution operator enjoys associativity and confluence properties quite similar to those of context-free graph grammars, and the membership problem for adaptive star grammars is decidable.
an nlogn algorithm for hyper-minimizing a (minimized) deterministic automaton. we improve a recent result [a. badr, hyper-minimization in o(n^2), internat. j. found. comput. sci. 20 (4) (2009) 735-746] for hyper-minimized finite automata. namely, we present an o(nlogn) algorithm that computes for a given deterministic finite automaton (dfa) an almost-equivalent dfa that is as small as possible-such an automaton is called hyper-minimal. here two finite automata are almost-equivalent if and only if the symmetric difference of their languages is finite. in other words, two almost-equivalent automata disagree on acceptance on finitely many inputs. in this way, we solve an open problem stated in [a. badr, v. geffert, i. shipman, hyper-minimizing minimized deterministic finite state automata, rairo theor. inf. appl. 43 (1) (2009) 69-94] and by badr. moreover, we show that minimization linearly reduces to hyper-minimization, which shows that the time-bound o(nlogn) is optimal for hyper-minimization. independently, similar results were obtained in [p. gawrychowski, a. jez, hyper-minimisation made efficient, in: proc. 34th int. symp. mathematical foundations of computer science, in: lncs, vol. 5734, springer, 2009, pp. 356-368].