waashk/dblp huggingface dataset:
nondeterministic functions and the existence of optimal proof systems. we provide new characterizations of two previously studied questions on nondeterministic function classes: q1: do nondeterministic functions admit efficient deterministic refinements? q2: do nondeterministic function classes contain complete functions? we show that q1 for the class npmv"t is equivalent to the question whether the standard proof system for sat is p-optimal, and to the assumption that every optimal proof system is p-optimal. assuming only the existence of a p-optimal proof system for sat, we show that every set with an optimal proof system has a p-optimal proof system. under the latter assumption, we also obtain a positive answer to q2 for the class npmv"t. an alternative view on nondeterministic functions is provided by disjoint sets and tuples. we pursue this approach for disjoint np-pairs and its generalizations to tuples of sets from np and conp with disjointness conditions of varying strength. in this way, we obtain new characterizations of q2 for the class npsv. question q1 for npsv is equivalent to the question of whether every disjoint np-pair is easy to separate. in addition, we characterize this problem by the question of whether every propositional proof system has the effective interpolation property. again, these interpolation properties are intimately connected to disjoint np-pairs, and we show how different interpolation properties can be modeled by np-pairs associated with the underlying proof system.
shortest synchronizing strings for huffman codes. most complete binary prefix codes have a synchronizing string, that is a string that resynchronizes the decoder regardless of its previous state. this work presents an upper bound on the length of the shortest synchronizing string for such codes. two classes of codes with a long shortest synchronizing string are presented. it is known that finding a synchronizing string for a code is equivalent to finding a synchronizing string of some finite automaton. the cerny conjecture for this class of automata is discussed.
overlap-free words and spectra of matrices. overlap-free words are words over the binary alphabet a={a,b} that do not contain factors of the form xvxvx, where x@?a and v@?a^*. we analyze the asymptotic growth of the number u"n of overlap-free words of length n as n->~. we obtain explicit formulas for the minimal and maximal rates of growth of u"n in terms of spectral characteristics (the joint spectral subradius and the joint spectral radius) of certain sets of matrices of dimension 20x20. using these descriptions we provide new estimates of the rates of growth that are within 0.4% and 0.03% of their exact values. the best previously known bounds were within 11% and 3%, respectively. we then prove that the value of u"n actually has the same rate of growth for ''almost all'' natural numbers n. this average growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the lyapunov exponent). we use this expression to estimate it. in order to obtain our estimates, we introduce new algorithms to compute the spectral characteristics of sets of matrices. these algorithms can be used in other contexts and are of independent interest.
modeling and simulation of cardiac tissue using hybrid i/o automata. we propose a new biological framework based on the lynch et al. theory of hybrid i/o automata (hioas) for modeling and simulating excitable tissue. within this framework, we view an excitable tissue as a composition of two main kinds of component: a diffusion medium and a collection of cells, both modeled as an hioa. this approach yields a notion of decomposition that allows us to describe a tissue as the parallel composition of several interacting tissues, a property that could be exploited to parallelize, and hence improve, the efficiency of the simulation process. we also demonstrate the feasibility of our hioa-based framework to capture and mimic different kinds of wave-propagation behavior in 2d isotropic cardiac tissue, including normal wave propagation along the tissue; the creation of spiral waves; the break-up of spiral waves into more complex patterns such as fibrillation; and the recovery of the tissue to the rest via electrical defibrillation.
a fast algorithm for finding the positions of all squares in a run-length encoded string. squares are strings of the form ww where w is any nonempty string. main and lorentz proposed an o(nlogn)-time algorithm for finding the positions of all squares in a string of length n. based on their result, we show how to find the positions of all squares in a run-length encoded string in time o(nlogn) where n is the number of runs in this string, provided that we do not explicitly compute at all ''trivial squares'' occurring within runs. the algorithm is optimal and its time complexity is independent of the length of the original uncompressed string.
a curtis-hedlund-lyndon theorem for besicovitch and weyl spaces. global functions of cellular automata on state spaces equipped with the cantor topology are well characterized by the curtis-hedlund-lyndon theorem. in this paper, we develop a characterization of global functions of cellular automata on z, if the state space is equipped by weyl and besicovitch topology. the necessary and sufficient condition for a function to be the global map of a cellular automaton is (1) a strong localization property, a condition that strengthen lipschitz continuity, (2) the set of (cantor) periodic states are positively invariant and (3) the function commutes (in the weyl/besicovitch sense) with the shift operator.
coordination mechanisms. we introduce the notion of coordination mechanisms to improve the performance in systems with independent selfish and non-colluding agents. the quality of a coordination mechanism is measured by its price of anarchy-the worst-case performance of a nash equilibrium over the (centrally controlled) social optimum. we give upper and lower bounds for the price of anarchy for selfish task allocation and congestion games.
deciding determinism of caterpillar expressions. caterpillar expressions have been introduced by bruggemann-klein and wood for applications in markup languages. caterpillar expressions provide a convenient formalism for specifying the operation of tree-walking automata on unranked trees. here we give a formal definition of determinism of caterpillar expressions that is based on the language of instruction sequences defined by the expression. we show that determinism of caterpillar expressions can be decided in polynomial time.
an analysis of the exponential decay principle in probabilistic trust models. research in models for experience-based trust management has either ignored the problem of modelling and reasoning about dynamically changing principal behaviour, or provided ad hoc solutions to it. probability theory provides a foundation for addressing this and many other issues in a rigorous and mathematically sound manner. using hidden markov models to represent principal behaviours, we focus on computational trust frameworks based on the 'beta' probability distribution and the principle of exponential decay, and derive a precise analytical formula for the estimation error they induce. this allows potential adopters of beta-based computational trust frameworks and algorithms to better understand the implications of their choice.
on the limits of the communication complexity technique for proving lower bounds on the size of minimal nfa's. in contrast to the minimization of deterministic finite automata (dfa's), the task of constructing a minimal nondeterministic finite automaton (nfa) for a given nfa is pspace-complete. moreover, there are no polynomial approximation algorithms with a constant approximation ratio for estimating the number of states of minimal nfa's. since one is unable to efficiently estimate the size of a minimal nfa in an efficient way, one should ask at least for developing mathematical proof methods that help to prove good lower bounds on the size of a minimal nfa for a given regular language. here we consider the robust and most successful lower bound proof technique that is based on communication complexity. in this paper it is proved that even a strong generalization of this method fails for some concrete regular languages. ''to fail'' is considered here in a very strong sense. there is an exponential gap between the size of a minimal nfa and the achievable lower bound for a specific sequence of regular languages. the generalization of the concept of communication protocols is also strong here. it is shown that cutting the input word into 2^o^(^n^^^1^^^/^^^4^) pieces for a size n of a minimal nondeterministic finite automaton and investigating the necessary communication transfer between these pieces as parties of a multiparty protocol does not suffice to get good lower bounds on the size of minimal nondeterministic automata. it seems that for some regular languages one cannot really abstract from the automata model that cuts the input words into particular symbols of the alphabet and reads them one by one using its input head.
on designing truthful mechanisms for online scheduling. we study the online version of the scheduling problem q@?c"m"a"x involving selfish agents, considered by archer and tardos in [a. archer, e. tardos, truthful mechanisms for one-parameter agents, in: proceedings of the 42nd ieee symposium on foundations of computer science (focs), 2001, pp. 482-491], where jobs must be scheduled on m related machines, each of them owned by a different selfish agent. we present a general technique for transforming competitive online algorithms for q@?c"m"a"x into truthful online mechanisms with a small loss of competitiveness. we also investigate the issue of designing new online algorithms from scratch so as to obtain efficient competitive mechanisms, and prove some lower bounds on a class of ''natural'' algorithms. a ''direct'' use of such natural algorithms to construct truthful mechanisms yields only trivial upper bounds for the case of two machines. finally, we consider mechanisms with verification, introduced by nisan and ronen [n. nisan, a. ronen, algorithmic mechanism design, in: proceedings of the 31st annual acm symposium on theory of computing, stoc, 1999, pp. 129-140], for offline scheduling problems. we present the first constant-competitive online truthful mechanism with verification for any number of machines.
on the satisfiability threshold of formulas with three literals per clause. in this paper we present a new upper bound for randomly chosen 3-cnf formulas. in particular we show that any random formula over n variables, with a clauses-to-variables ratio of at least 4.4898 is, as n grows large, asymptotically almost surely unsatisfiable. the previous best such bound, due to dubois in 1999, was 4.506. the first such bound, independently discovered by many groups of researchers since 1983, was 5.19. several decreasing values between 5.19 and 4.506 were published in the years between. we believe that the probabilistic techniques we use for the proof are of independent interest.
strip packing with precedence constraints and strip packing with release times. the strip packing problem seeks to tightly pack a set of n rectangles into a strip of fixed width and arbitrary height. the rectangles model tasks and the height models time. this paper examines two variants of strip packing: when the rectangles to be placed have precedence constraints and when the rectangles have release times. strip packing is used to model scheduling problems in which tasks require a contiguous subset of identical resources that are arranged in a linear topology. the variants studied here are motivated by scheduling tasks for dynamically reconfigurable field-programmable gate arrays (fpgas) comprised of a linear arrangement of k homogeneous computing resources, where k is a fixed positive integer, and each task occupies a contiguous subset of these resources. for the case in which tasks have precedence constraints, we give an o(logn) approximation algorithm. we then consider the special case in which all the rectangles have uniform height, and reduce it to the resource constrained scheduling studied by garey, graham, johnson and yao, thereby extending their asymptotic results to our special case problem. we also give an absolute 3-approximation for this special case problem. for strip packing with release times, we provide an asymptotic polynomial time approximation scheme. we make the standard assumption that the rectangles have height at most 1. in addition, we also require widths to be in [1k,1]. for the fpga application, this would imply that the rectangles are at least as wide as a column. our running time is polynomial in n and 1/@e, but exponential in k.
the complexity of weighted boolean #csp with mixed signs. we give a complexity dichotomy for the problem of computing the partition function of a weighted boolean constraint satisfaction problem. such a problem is parameterized by a set @c of rational-valued functions, which generalize constraints. each function assigns a weight to every assignment to a set of boolean variables. our dichotomy extends previous work in which the weight functions were restricted to being non-negative. we represent a weight function as a product of the form (-1)^sg, where the polynomial s determines the sign of the weight and the non-negative function g determines its magnitude. we show that the problem of computing the partition function (the sum of the weights of all possible variable assignments) is in polynomial time if either every function in @c can be defined by a ''pure affine'' magnitude with a quadratic sign polynomial or every function can be defined by a magnitude of ''product type'' with a linear sign polynomial. in all other cases, computing the partition function is fp^#^p-complete.
a powerful abelian square-free substitution over 4 letters. in 1961, paul erdos posed the question whether abelian squares can be avoided in arbitrarily long words over a finite alphabet. an abelian square is a non-empty word uv, where u and v are permutations (anagrams) of each other. the case of the four letter alphabet @s"4={a,b,c,d} turned out to be the most challenging and remained open until 1992 when the author presented an abelian square-free (a-2-free) endomorphism g"8"5 of @s"4^*. the size of this g"8"5, i.e., |g"8"5(abcd)|, is equal to 4x85 (uniform modulus). until recently, all known methods for constructing arbitrarily long a-2-free words on @s"4 have been based on the structure of g"8"5 and on the endomorphism g"9"8 of @s"4^* found in 2002. in this paper, a great many new a-2-free endomorphisms of @s"4^* are reported. the sizes of these endomorphisms range from 4x102 to 4x115. importantly, twelve of the new a-2-free endomorphisms, of modulus m=109, can be used to construct an a-2-free (commutatively functional) substitution @s"1"0"9 of @s"4^* with 12 image words for each letter. the properties of @s"1"0"9 lead to a considerable improvement for the lower bound of the exponential growth of c"n, i.e., of the number of a-2-free words over 4 letters of length n. it is obtained that c"n>@b^-^5^0@b^n with @b=12^1^/^m~1.02306. originally, in 1998, carpi established the exponential growth of c"n by showing that c"n>@b^-^t@b^n with @b=2^1^9^/^t=2^1^9^/^(^8^5^^^3^-^8^5^)~1.000021, where t=85^3-85 is the modulus of the substitution that he constructs starting from g"8"5.
isolation concepts for efficiently enumerating dense subgraphs. in an undirected graph g=(v,e), a set of k vertices is called c-isolated if it has less than c@?k outgoing edges. ito and iwama [h. ito, k. iwama, enumeration of isolated cliques and pseudo-cliques, acm transactions on algorithms (2008) (in press)] gave an algorithm to enumerate all c-isolated maximal cliques in o(4^c@?c^4@?|e|) time. we extend this to enumerating all maximal c-isolated cliques (which are a superset) and improve the running time bound to o(2.89^c@?c^2@?|e|), using modifications which also facilitate parallelizing the enumeration. moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. finally, we extend our considerations to s-plexes (a relaxation of the clique notion), providing a w[1]-hardness result when the size of the s-plex is the parameter and a fixed-parameter algorithm for enumerating isolated s-plexes when the parameter describes the degree of isolation.
some operations preserving primitivity of words. we investigate some operations where essentially, from a given word w, the word ww^' is constructed where w^' is a modified copy of w or a modified mirror image of w. we study whether ww^' is a primitive word provided that w is primitive. for instance, we determine all cases with an edit distance of w and w^' at most 2 such that the primitivity of w implies the primitivity of ww^'. the operations are chosen in such a way that in the case of a two-letter alphabet, all primitive words of length @?11 can be obtained from single letters.
reoptimization of steiner trees: changing the terminal set. given an instance of the steiner tree problem together with an optimal solution, we consider the scenario where this instance is modified locally by adding one of the vertices to the terminal set or removing one vertex from it. in this paper, we investigate the problem of whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. our results are as follows: (i) we prove that these reoptimization variants of the steiner tree problem are np-hard, even if edge costs are restricted to values from {1,2}. (ii) we design 1.5-approximation algorithms for both variants of local modifications. this is an improvement over the currently best known approximation algorithm for the classical steiner tree problem which achieves an approximation ratio of 1+ln(3)/2~1.55. (iii) we present a ptas for the subproblem in which the edge costs are natural numbers {1,...,k} for some constant k.
online scheduling on two uniform machines subject to eligibility constraints. we consider the online scheduling of a set of jobs on two uniform machines with the makespan as objective. the jobs are presented in a list. we consider two different eligibility constraint set assumptions, namely (i) arbitrary eligibility constraints and (ii) grade of service (gos) eligibility constraints. in the first case, we prove that the high speed machine first (hsf) algorithm, which assigns jobs to the eligible machine that has the highest speed, is optimal. with regard to the second case, we point out an error in [m. liu et al., online scheduling on two uniform machines to minimize the makespan, theoretical computer science 410 (21-23) (2009) 2099-2109]; we then provide tighter lower bounds and present algorithms with worst-case analysis for various ranges of machine speeds.
on systems of word equations over three unknowns with at most six occurrences of one of the unknowns. in this paper, we investigate the open question, formulated in 1983 by culik ii and karhumaki, asking whether there exist independent systems of three word equations over three unknowns admitting non-periodic solutions. in particular, we answer negatively the above mentioned question for systems in which one of the unknowns occurs at most six times. that is, we show that such systems admit only periodic solutions or they are not independent.
online scheduling on m uniform machines to minimize total (weighted) completion time. we study two online problems on m uniform machines with speeds s"1@?...@?s"m. the problems are online in the sense that all jobs arrive over time. each job's characteristics, such as processing time and weight become known at its arrival time. for the first problem q|r"j,online|@?c"j, we prove that r-list algorithm is 4m-3+32-competitive. for the second problem q|r"j,online,pmtn|@?w"jc"j, we show that wspt-1 algorithm is 2-competitive if s"i/s"m>=@?"h"="1^is"h/@?"h"="1^ms"h for i=1,...,m-1. then we study a special case where s"1=s"2=...=s"m"-"1@?s"m. we obtain that algorithm wspt-1 is 2-competitive if s"m(m-2)@?s"1(m-1).
the structure and complexity of nash equilibria for a selfish routing game. in this work, we study the combinatorial structure and the computational complexity of nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. in a nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. the social cost of a nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. we embark on a systematic study of several algorithmic problems related to the computation of nash equilibria for the selfish routing game we consider. in a nutshell, these problems relate to deciding the existence of a pure nash equilibrium, constructing a nash equilibrium, constructing the pure nash equilibria of minimum and maximum social cost, and computing the social cost of a given mixed nash equilibrium. our work provides a comprehensive collection of efficient algorithms, hardness results, and structural results for these algorithmic problems. our results span and contrast a wide range of assumptions on the syntax of the nash equilibria and on the parameters of the system.
efficient construction of maximal and minimal representations of motifs of a string. two substrings of a given text string are called synchronous (occurrence-equivalent) if their sets of occurrence locations are translates of each other. linear time algorithms are given for the problems of finding a shortest and a longest substring that is synchronous with a given substring. we also introduce approximate variants of the motif discovery problem and give polynomial time algorithms for finding longest and shortest substrings whose suitably translated occurrence location set contains or, respectively, is contained in a given set of locations. the fft technique used here also leads to an o(nlogn) algorithm for finding the maximum-content gapped motif that is synchronous with a given set of locations; the previously known algorithm for this problem is only quadratic.
efficient enumeration of words in regular languages. the cross-section enumeration problem is to list all words of length n in a regular language l in lexicographical order. the enumeration problem is to list the first m words in l according to radix order. we present an algorithm for the cross-section enumeration problem that is linear in n+t, where t is the output size. we provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. we discuss some shortcomings of the enumeration algorithm found in the grail computation package. in the practical domain, we modify makinen's enumeration algorithm to get an algorithm that is usually the most efficient in practice. we performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable.