waashk/dblp huggingface dataset:
non-strict independence-based program parallelization using sharing and freeness information. the current ubiquity of multi-core processors has brought renewed interest in program parallelization. logic programs allow studying the parallelization of programs with complex, dynamic data structures with (declarative) pointers in a comparatively simple semantic setting. in this context, automatic parallelizers which exploit and-parallelism rely on notions of independence in order to ensure certain efficiency properties. ''non-strict'' independence is a more relaxed notion than the traditional notion of ''strict'' independence which still ensures the relevant efficiency properties and can allow considerable more parallelism. non-strict independence cannot be determined solely at run-time (''a priori'') and thus global analysis is a requirement. however, extracting non-strict independence information from available analyses and domains is non-trivial. this paper provides on one hand an extended presentation of our classic techniques for compile-time detection of non-strict independence based on extracting information from (abstract interpretation-based) analyses using the now well understood and popular sharing+freeness domain. this includes algorithms for combined compile-time/run-time detection which involve special run-time checks for this type of parallelism. in addition, we propose herein novel annotation (parallelization) algorithms, urlp and crlp, which are specially suited to non-strict independence. we also propose new ways of using the sharing+freeness information to optimize how the run-time environments of goals are kept apart during parallel execution. finally, we also describe the implementation of these techniques in our parallelizing compiler and recall some early performance results. we provide as well an extended description of our pictorial representation of sharing and freeness information.
approximating the maximum internal spanning tree problem. given an undirected connected graph g we consider the problem of finding a spanning tree of g which has a maximum number of internal (non-leaf) vertices among all spanning trees of g. this problem, called maximum internal spanning tree problem, is clearly np-hard since it is a generalization of the hamiltonian path problem. from the optimization point of view the maximum internal spanning tree problem is equivalent to the minimum leaf spanning tree problem. however, the two problems have different approximability properties. lu and ravi proved that the latter has no constant factor approximation-unless p = np-, while salamon and wiener gave a linear-time 2-approximation algorithm for the maximum internal spanning tree problem. in this paper, we improve this approximation ratio by giving an o(|v(g)|^4)-time7/4-approximation algorithm for graphs without pendant vertices. our approach is based on the successive execution of local improvement steps. we use a linear programming formulation and a primal-dual technique to prove the approximation ratio. we also investigate the vertex-weighted case, that is to find a spanning tree of a vertex-weighted graph g in which the weight sum of internal vertices is maximal among all spanning trees of g. for this problem we present a (2@d(g)-3)-approximation algorithm, where @d(g) is the maximum vertex-degree of g. a slight modification of this algorithm ensures a 2-approximation whenever the input graph is claw-free. both algorithms run in o(|v(g)|^4) time for graphs with no pendant vertices.
necessary and sufficient conditions for learning with correction queries. we investigate the newly introduced model of learning with correction queries in the context of query learning. we present necessary and sufficient conditions for a class of languages to be inferable within this setting. we also offer a complete picture of how is the model of learning with corrections related with other well-established learning models, like the model of learning in the limit from positive data, or the one of learning with membership queries. as an application, we show that the class of k-reversible languages is learnable with correction queries.
searching for gapped palindromes. we study the problem of finding, in a given word, all maximal gapped palindromes verifying two types of constraints, that we call long-armed and length-constrained palindromes. for each of the two classes, we propose an algorithm that runs in time o(n+s) for a constant-size alphabet, where s is the number of output palindromes. both algorithms can be extended to compute biological gapped palindromes within the same time bound.
parameterized learnability of juntas. we study the parameterized complexity of learning k-juntas and some variations of juntas. we show the hardness of learning k-juntas and subclasses of k-juntas in the pac model by reductions from a w[2]-complete problem. on the other hand, as a consequence of a more general result, we show that k-juntas are exactly learnable with improper equivalence queries and access to a w[p] oracle.
a four-stage algorithm for updating a burrows-wheeler transform. we present a four-stage algorithm that updates the burrows-wheeler transform of a text t, when this text is modified. the burrows-wheeler transform is used by many text compression applications and some self-index data structures. it operates by reordering the letters of a text t to obtain a new text bwt(t) which can be better compressed. even though recent advances are offering this structure new applications, a major bottleneck still exists: bwt(t) has to be entirely reconstructed from scratch whenever t is modified. we study how standard edit operations (insertion, deletion, substitution of a letter or a factor) that transform a text t into t^' impact bwt(t). then we present an algorithm that directly converts bwt(t) into bwt(t^'). based on this algorithm, we also sketch a method for converting the suffix array of t into the suffix array of t^'. we finally show, based on the experiments we conducted, that this algorithm, whose worst-case time complexity is o(|t|log|t|(1+log@s/loglog|t|)), performs really well in practice and replaces advantageously the traditional approach.
the subsequence composition of a string. words that appear as constrained subsequences in a text-string are considered as possible indicators of the host string structure, hence also as a possible means of sequence comparison and classification. the constraint consists of imposing a bound on the number @w of positions in the text that may intervene between any two consecutive characters of a subsequence. a subset of such @w-sequences is then characterized that consists, in intuitive terms, of sequences that could not be enriched with more characters without losing some occurrence in the text. a compact spatial representation is then proposed for these representative sequences, within which a number of parameters can be defined and measured. in the final part of the paper, such parameters are empirically analyzed on a small collection of text-strings endowed with various degrees of structure.
approximating maximum edge 2-coloring in simple graphs via local improvement. we present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. it achieves an approximation ratio of 2429~0.828.
a combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation. the problem of two-dimensional pattern matching invariant under a given class of admissible transformations f is to find matches of transformed versions f(p) of a pattern p in a given text t, for all f in f. in this paper, pattern matching invariant under compositions of real valued scaling and rotation are investigated. we give a new discretization technique for this class of transformations and prove sharp lower and upper bounds on the number of different possibilities to transform a pattern in this way. subsequently, we present the first efficient pattern matching algorithm invariant under compositions of scaling and rotation. the algorithm works in time o(m^2n^6) for patterns of size m^2 and texts of size n^2. we conclude with an experimental section to support the practical use of our results.
completing codes in a sofic shift. we define a code in a sofic shift as a set of blocks of symbols of the shift such that any block of the shift has at most one decomposition into code words. it is maximal if it is not strictly included in another one. such a code is complete in the sofic shift if any block of the shift occurs within some concatenation of code words. we prove that a maximal code in an irreducible sofic shift is complete in this shift. we give an explicit construction of a regular completion of a regular code in a sofic shift. this extends the well known result of ehrenfeucht and rozenberg to the case of codes in sofic systems. we also give a combinatorial proof of a result concerning the polynomial of a code in a sofic shift.
fixed-parameter algorithms for kemeny rankings. the computation of kemeny rankings is central to many applications in the context of rank aggregation. given a set of permutations (votes) over a set of candidates, one searches for a ''consensus permutation'' that is ''closest'' to the given set of permutations. unfortunately, the problem is np-hard. we provide a broad study of the parameterized complexity for computing optimal kemeny rankings. besides the three obvious parameters ''number of votes'', ''number of candidates'', and solution size (called kemeny score), we consider further structural parameterizations. more specifically, we show that the kemeny score (and a corresponding kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. in other words, kemeny score is fixed-parameter tractable with respect to the parameter ''average pairwise kendall-tau distance d"a''. we describe a fixed-parameter algorithm with running time 16^@?^d^"^a^@?@?poly. moreover, we extend our studies to the parameters ''maximum range'' and ''average range'' of positions a candidate takes in the input votes. whereas kemeny score remains fixed-parameter tractable with respect to the parameter ''maximum range'', it becomes np-complete in the case of an average range of two. this excludes fixed-parameter tractability with respect to the parameter ''average range'' unless p=np. finally, we extend some of our results to votes with ties and incomplete votes, where in both cases one no longer has permutations as input.
faster entropy-bounded compressed suffix trees. suffix trees are among the most important data structures in stringology, with a number of applications in flourishing areas like bioinformatics. their main problem is space usage, which has triggered much research striving for compressed representations that are still functional. a smaller suffix tree representation could fit in a faster memory, outweighing by far the theoretical slowdown brought by the space reduction. we present a novel compressed suffix tree, which is the first achieving at the same time sublogarithmic complexity for the operations, and space usage that asymptotically goes to zero as the entropy of the text does. the main ideas in our development are compressing the longest common prefix information, totally getting rid of the suffix tree topology, and expressing all the suffix tree operations using range minimum queries and a novel primitive called next/previous smaller value in a sequence. our solutions to those operations are of independent interest.
on the algebraic structure of declarative programming languages. we develop an algebraic framework, logic programming doctrines, for the syntax, proof theory, operational semantics and model theory of horn clause logic programming based on indexed premonoidal categories. our aim is to provide a uniform framework for logic programming and its extensions capable of incorporating constraints, abstract data types, features imported from other programming language paradigms and a mathematical description of the state space in a declarative manner. we define a new way to embed information about data into logic programming derivations by building a sketch-like description of data structures directly into an indexed category of proofs. we give an algebraic axiomatization of bottom-up semantics in this general setting, describing categorical models as fixed points of a continuous operator.
expander properties and the cover time of random intersection graphs. we investigate important combinatorial and algorithmic properties of g"n","m","p random intersection graphs. in particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are ''rapidly mixing'' (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is @q(nlogn)). all results are proved for p very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical g"n","p random graphs.
masking patterns in sequences: a new class of motif discovery with don't cares. we introduce a new notion of motifs, called masks, that succinctly represents the repeated patterns for an input sequence t of n symbols drawn from an alphabet @s. we show how to build the set of all frequent maximal masks of length l in o(2^ln) time and space in the worst case, using the karp-miller-rosenberg approach. we analytically show that our algorithm performs better than the method based on constant-time enumerating and checking all the potential (|@s|+1)^l candidate patterns in t, after a polynomial-time preprocessing of t. our algorithm is also cache-friendly, attaining o(2^lsort(n)) block transfers, where sort(n) is the cache complexity of sorting n items.
vpspace and a transfer theorem over the complex field. we extend the transfer theorem of [14] to the complex field. that is, we investigate the links between the class vpspace of families of polynomials and the blum-shub-smale model of computation over c. roughly speaking, a family of polynomials is in vpspace if its coefficients can be computed in polynomial space. our main result is that if (uniform, constant-free) vpspace families can be evaluated efficiently, then the class par"c of decision problems that can be solved in parallel polynomial time over the complex field collapses to p"c. as a result, one must first be able to show that there are vpspace families which are hard to evaluate in order to separate p"c from np"c, or even from par"c.
circular sturmian words and hopcroft's algorithm. in order to analyze some extremal cases of hopcroft's algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton a"x associated to (x). the combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. we prove that the shape of this tree uniquely characterizes the word itself. the properties of the run of hopcroft's algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of hopcroft's algorithm, leads to the coarsest congruence of the automaton. we prove that the shape of the reduction tree of a circular sturmian word (x) coincides with that of the derivation tree t(a"x) of the automaton a"x. from this we derive a recursive formula to compute the running time of hopcroft's algorithm on the automaton a"x, expressed in terms of parameters of the reduction tree of (x). as a special application, we obtain the time complexity @q(nlogn) of the algorithm in the case of automata associated to fibonacci words.
on the computational complexity of the languages of general symbolic dynamical systems and beta-shifts. we consider the computational complexity of languages of symbolic dynamical systems. in particular, we study complexity hierarchies and membership of the non-uniform class p/poly. we prove: 1.for every time-constructible, non-decreasing function t(n)=@w(n), there is a symbolic dynamical system with language decidable in deterministic time o(n^2t(n)), but not in deterministic time o(t(n)). 2.for every space-constructible, non-decreasing function s(n)=@w(n), there is a symbolic dynamical system with language decidable in deterministic space o(s(n)), but not in deterministic space o(s(n)). 3.there are symbolic dynamical systems having hard and complete languages under @?"m^l^o^g^s- and @?"m^p-reduction for every complexity class above logspace in the backbone hierarchy (hence, p-complete, np-complete, conp-complete, pspace-complete, and exptime-complete sets). 4.there are decidable languages of symbolic dynamical systems in p/poly for every alphabet of size |@s|>=1. 5.there are decidable languages of symbolic dynamical systems not in p/poly iff the alphabet size is >1. for the particular class of symbolic dynamical systems known as @b-shifts, we prove that: 1.for all real numbers @b>1, the language of the @b-shift is in p/poly. 2.if there exists a real number @b>1 such that the language of the @b-shift is np-hard under @?"t^p-reduction, then the polynomial hierarchy collapses to the second level. as np-hardness under @?"m^p-reduction implies hardness under @?"t^p-reduction, this result implies that it is unlikely that a proof of existence of an np-hard language of a @b-shift will be forthcoming. 3.for every time-constructible, non-decreasing function t(n)>=n, there is a real number 1
interchange rearrangement: the element-cost model. given an input string s and a target string t when s is a permutation of t, the interchange rearrangement problem is to apply on s a sequence of interchanges, such that s is transformed into t. the interchange operation exchanges the position of the two elements on which it is applied. the goal is to transform s into t at the minimum cost possible, referred to as the distance between s and t. the distance can be defined by several cost models that determine the cost of every operation. there are two known models: the unit-cost model and the length-cost model. in this paper, we suggest a natural cost model: the element-cost model. in this model, the cost of an operation is determined by the elements that participate in it. though this model has been studied in other fields, it has never been considered in the context of rearrangement problems. we consider both the special case where all elements in s and t are distinct, referred to as a permutation string, and the general case, referred to as a general string. an efficient optimal algorithm for the permutation string case and efficient approximation algorithms for the general string case, which is np-hard, are presented. the study is broadened to include the transposition rearrangement problem under the element-cost model and under the other known models, in order to provide additional perspective on the new model.
applications of polyhedral computations to the analysis and verification of hardware and software systems. convex polyhedra are the basis for several abstractions used in static analysis and computer-aided verification of complex and sometimes mission-critical systems. for such applications, the identification of an appropriate complexity-precision trade-off is a particularly acute problem, so that the availability of a wide spectrum of alternative solutions is mandatory. we survey the range of applications of polyhedral computations in this area; give an overview of the different classes of polyhedra that may be adopted; outline the main polyhedral operations required by automatic analyzers and verifiers; and look at some possible combinations of polyhedra with other numerical abstractions that have the potential to improve the precision of the analysis. areas where further theoretical investigations can result in important contributions are highlighted.
a push-relabel approximation algorithm for approximating the minimum-degree mst problem and its generalization to matroids. in the minimum-degree minimum spanning tree (mdmst) problem, we are given a graph g, and the goal is to find a minimum spanning tree (mst) t, such that the maximum degree of t is as small as possible. this problem is np-hard and generalizes the hamiltonian path problem. we give an algorithm that outputs an mst of degree at most 2@d"o"p"t" (g)+o(@d"o"p"t" (g)), where @d"o"p"t" (g) denotes the degree of the optimal tree. this result improves on a previous result of fischer [t. fischer, optimizing the degree of minimum weight spanning trees. technical report 14853, dept. of computer science, cornell university, ithaca, ny, 1993] that finds an mst of degree at most b@d"o"p"t" (g)+log"bn, for any b>1. the mdmst problem is a special case of the following problem: given a k-ary hypergraph g=(v,e) and weighted matroid m with e as its ground set, find a minimum-cost basis (mcb) t of m such that the degree of t in g is as small as possible. our algorithm immediately generalizes to this problem, finding an mcb of degree at most k^2@d"o"p"t" (g,m)+o(kk@d"o"p"t" (g,m)). we use the push-relabel framework developed by goldberg [a. v. goldberg, a new max-flow algorithm, technical report mit/lcs/tm-291, massachusetts institute of technology, 1985 (technical report)] for the maximum-flow problem. to our knowledge, this is the first use of the push-relabel technique in an approximation algorithm for an np-hard problem. the mdmst problem is closely connected to the bounded-degree minimum spanning tree (bdmst) problem. given a graph g and degree bound b on its nodes, the bdmst problem is to find a minimum cost spanning tree among the spanning trees with maximum degree b. previous algorithms for this problem by konemann and ravi [j. konemann, r. ravi, a matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees, siam journal on computing 31(6) (2002) 1783-1793; j. konemann, r. ravi, primal-dual meets local search: approximating mst's with nonuniform degree bounds, in: proceedings of the thirty-fifth acm symposium on theory of computing, 2003, pp. 389-395] and by chaudhuri et al. [k. chaudhuri, s. rao, s. riesenfeld, k. talwar, what would edmonds do? augmenting paths and witnesses for bounded degree msts, in: proceedings of approx/random, 2005, pp. 26-39] incur a near-logarithmic additive error in the degree. we give the first bdmst algorithm that approximates both the degree and the cost to within a constant factor of the optimum. these results generalize to the case of nonuniform degree bounds.
scheduling with families of jobs and delivery coordination under job availability. we consider in this paper the scheduling of families of jobs in which both processing and delivery are coordinated together. only one vehicle is available to deliver the jobs to specified customers. the jobs can be processed together to form processing batches on the machine and setups of batches are required when the machine is changing from one family to another. jobs from different families cannot be transported together by the vehicle. the objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. we propose an o(nlogn)-time optimal algorithm for the scheduling problem under the group technology assumption. for the scheduling problem without the group technology assumption, we show that the problem is np-hard and give an o(f^2n^f)-time dynamic programming algorithm, where n is the number of jobs, and f is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2.