waashk/dblp huggingface dataset:
on-line scheduling of parallel jobs with runtime restrictions. consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. we assume that there is not suffucient knowledge about the running times and the number of jobs generated in order to precompute a schedule for such applications. rather, the scheduling decisions have to be made on-line during runtime based on incomplete information. we present several on-line scheduling algorithms for various interconnection topologies that use some a priori information about the job running times or guarantee a good competitive ratio that depends on the runtime ratio of all generated jobs. all algorithms presented have optimal competitive ratio up to small additive constants, and are easy to implement. copyright 2001 elsevier science b.v.
memoryless determinacy of parity and mean payoff games: a simple proof. we give a simple, direct, and constructive proof of memoryless determinacy for parity and mean payoff games. first, we prove by induction that the finite duration versions of these games, played until some vertex is repeated, are determined and both players have memoryless winning strategies. in contrast to the proof of ehrenfeucht and mycielski, internat. j. game theory, 8 (1979) 109-113, our proof does not refer to the infinite-duration versions. second, we show that memoryless determinacy straightforwardly generalizes to infinite duration versions of parity and mean payoff games.
combinatorial structure and randomized subexponential algorithms for infinite games. the complexity of solving infinite games, including parity, mean payoff, and simple stochastic, is an important open problem in verification, automata, and complexity theory. in this paper, we develop an abstract setting for studying and solving such games, based on function optimization over certain discrete structures. we introduce new classes of recursively local-global (rlg) and partial recursively local-global (prlg) functions, and show that strategy evaluation functions for simple stochastic, mean payoff, and parity games belong to these classes.in this setting, we suggest randomized subexponential algorithms appropriate for rlg-and prlg-function optimization. we show that the subexponential algorithms for combinatorial linear programming, due to kalai and matoušek, sharir, welzl, can be adapted for optimizing the rlg-and prlg-functions.
some results about the chaotic behavior of cellular automata. we study the behavior of cellular automata (ca for short) in the cantor, besicovitch and weyl topologies. we solve an open problem about the existence of transitive ca in the besicovitch topology. the proof of this result has some interest of its own since it is obtained by using kolmogorov complexity. to our knowledge it is the first result about discrete dynamical systems obtained using kolmogorov complexity. we also prove that in the besicovitch topology every ca has either a unique periodic point (thus a fixed point) or an uncountable set of periodic points. this result underlines the fact that ca have a great degree of stability; it may be considered a further step towards the understanding of ca periodic behavior.moreover, we prove that in the besicovitch topology there is a special set of configurations, the set of toeplitz configurations, that plays a role similar to that of spatially periodic configurations in the cantor topology, that is, it is dense and has a central role in the study of surjectivity and injectivity. finally, it is shown that the set of spatially quasi-periodic configurations is not dense in the weyl topology.
codes, orderings, and partial words. codes play an important role in the study of the combinatorics of words. in this paper, we introduce pcodes that play a role in the study of combinatorics of partial words. partial words are strings over a finite alphabet that may contain a number of "do not know" symbols. pcodes are defined in terms of the compatibility relation that considers two strings over the same alphabet that are equal except for a number of insertions and/or deletions of symbols. we describe various ways of defining and analyzing pcodes, in particular, many pcodes can be obtained as antichains with respect to certain partial orderings. using a technique related to dominoes, we show that the pcode property is decidable.
local periods and binary partial words: an algorithm. the study of the combinatorial properties of strings of symbols from a finite alphabet (also referred to as words) is profoundly connected to numerous fields such as biology, computer science, mathematics, and physics. research in combinatorics on words goes back roughly a century. there is a renewed interest in combinatorics on words as a result of emerging new application areas such as molecular biology. partial words were recently introduced in this context. the motivation behind the notion of a partial word is the comparison of genes (or proteins). alignment of two genes (or two proteins) can be viewed as a construction of partial words that are said to be compatible. while a word can be described by a total function, a partial word can be described by a partial function. more precisely, a partial word of length n over a finite alphabet a is a partial function from {1,...,n} into a. elements of {1,...,n} without an image are called holes. a word is just a partial word without holes. the notion of period of a word is central in combinatorics on words. in the case of partial words, there arc two notions: one is that of period, the other is that of local period. this paper extends to partial words with one hole the well known result of guibas and odlyzko which states that for every word u, there exists a word v of same length as u over the alphabet {0, 1} such that the set of all periods of u coincides with the set of all periods of v. our result states that for every partial word u with one hole, there exists a partial word v of same length as u with at most one hole over the alphabet {0, 1} such that the set of all periods of u coincides with the set of all periods of v and the set of all local periods of u coincides with the set of all local periods of v. to prove our result, we use the technique of halava, harju and ilie which they used to characterize constructively the set of periods of a given word. as a consequence of our constructive proof, we obtain a linear time algorithm which, given a partial word with one hole, computes a partial word with at most one hole over the alphabet {0, 1} with the same length and the same sets of periods and local periods. a world wide web server interface at http://www.uncg.edu/mat/algbin/ has been established for automated use of the program.
partial words and a theorem of fine and wilf revisited. a word of length n over a finite alphabet a is a map from {0,...,n_1} into a. a partial word of length n over a is a partial map from {0,...,n_1} into a. in the latter case, elements of {0,...,n1} without image are called holes (a word is just a partial word without holes). in this paper, we extend a fundamental periodicity result on words due to fine and wilf to partial words with two or three holes. this study was initiated by berstel and boasson for partial words with one hole. partial words are motivated by molecular biolog
conjugacy on partial words. the study of the combinatorial properties of strings of symbols from a finite alphabet (also referred to as words) is profoundly connected to numerous fields such as biology, computer science, mathematics, and physics. in this paper, we examine to which extent some fundamental combinatorial properties of words, such as conjugacy, remain true for partial words. the motivation behind the notion of a partial word is the comparison of two genes (alignment of two such strings can be viewed as a construction of two partial words that are said to be compatible). this study on partial words was initiated by berstel and boasson.
verification of cryptographic protocols: tagging enforces termination. we investigate a resolution-based verification method for secrecy and authentication properties of cryptographic protocols. in experiments, we could enforce its termination by tagging, a syntactic transformation of messages that leaves attack-free executions invariant. in this paper, we generalize the experimental evidence: we prove that the verification method always terminates for tagged protocols.
domain representations of partial functions, with applications to spatial objects and constructive volume geometry. a partial spatial object is a partial map from space to data. data types of partial spatial objects are modelled by topological algebras of partial maps and are the foundation for a high level approach to volume graphics called constructive volume geometry (cvg), where space and data are subspaces of n dimensional euclidean space. we investigate the computability of partial spatial object data types, in general and in volume graphics, using the theory of effective domain representations for topological algebras. the basic mathematical problem considered is to classify which partial functions between topological spaces can be represented by total continuous functions between given domain representations of the spaces. we prove theorems about partial functions on regular hausdorff spaces and their domain representations, and apply the results to partial spatial objects and cvg algebras.
inductive-data-type systems. in a previous work ("abstract data type systems", tcs 173(2), 1997), the last two authors presented a combined language made of a (strongly normalizing) algebraic rewrite system and a typed &lambda;-calculus enriched by pattern-matching definitions following a certain format, called the "general schema", which generalizes the usual recursor definitions for natural numbers and similar "basic inductive types". this combined language was shown to be strongly normalizing. the purpose of this paper is to reformulate and extend the general schema in order to make it easily extensible, to capture a more general class of inductive types, called "strictly positive", and to ease the strong normalization proof of the resulting system. this result provides a computation model for the combination of an algebraic specification language based on abstract data types and of a strongly typed functional language with strictly positive inductive types. copyright 2002 elsevier science b.v.
the complexity of bivariate power series arithmetic. inspired by schönhage's discussion in the proc. 11th applied algebra and error correcting codes conference (aaecc), lecture notes in comput. sci., springer, berlin, vol. 948, 1995 pp. 70, we study the multiplicative complexity of the multiplication, squaring, inversion, and division of bivariate power series modulo the "triangular" and "quadratic" ideals (xd+1, xdy,xd-1 y2,..., yd+1) and (xd+1, yd+1), respectively. for multiplication, we obtain the lower bounds 5/4 d2 - o(d) and 2 1/3 d2 o(d) for the triangular and quadratic case, respectively, opposed to the upper bounds 3/2 d2 + o(d) and 3d2 + o(d). for squaring, we prove the lower bounds 7/8 d2-o(d) and 1 3/5 d2- o(d). as upper bounds, we have d2+o(d) and 2 ½ d2+o(d) for the triangular and quadratic case, respectively. concerning inversion, the obtained lower bounds coincide with those of squaring. as upper bounds, we show 3 5/6 d2 + o(d) and 8 1/3 d2 + o(d), respectively. the lower bounds for division are those of multiplication. the upper bounds follow from combining the bounds for inversion and multiplication. all of the above lower bounds hold over arbitrary fields (in the case of multiplication and division) and over fields of characteristic distinct from two (in the case of squaring and inversion), respectively. all upper bounds are valid for fields that "support ffts", that is, fields that have characteristic zero and contain all roots of unity.
beyond the alder-strassen bound. we prove a lower bound of 5/2n2 - 3n for the multiplicative complexity of n × n-matrix multiplication over arbitrary fields. more general, we show that for any finite dimensional semisimple algebra a with unity, the multiplicative complexity c (a) of the multiplication in a is bounded from below by 5/2 dim a - 3(n1 +...+ nt) if the decomposition of a ≃ a1 × ... × at into simple algebras aτ ≃ dτnτ×nτ contains only noncommutative factors, that is, the division algebra dτ is noncommutative or nτ≥2.we also deal with the complexity of multiplication in algebras with nonzero radical. we present an example that shows that our methods in the semisimple case cannot be applied directly to this problem. we exhibit lower bound techniques for c(a) that yield bounds still significantly above the alder-strassen bound. the main application is the lower bound c (tn(k)) ≥ (21/8-o(1)) dim tn(k) for the multiplicative complexity of multiplication in the algebra tn(k) of upper triangular n × n-matrices.
orphan gene finding - an exon assembly approach. this paper introduces an algorithm for finding eukaryotic genes. it particularly addresses the problem of orphan genes, that is of genes that cannot, based on homology alone, be connected to any known gene family and to which it is therefore not possible to apply traditional gene finding methods. to the best of our knowledge, this is also the first algorithm that attempts to compare in an exact way two dna sequences that contain both coding (i.e. exonic) and non-coding (i.e. intronic and, possibly, intergenic) parts. the comparison is performed following an algorithmical model of a gene that is as close as possible to the biological one (we consider in this paper the "one orf, one gene" problem only). a gene is seen as a set of exons that are pieces of an assembly and are not independent. the algorithm is efficient enough: although the constants are higher than for usual sequence comparison, its time complexity is proportional to the product of the sequences lengths while its space complexity scales linearly with the length of the smallest sequence.
complexity of dna sequencing by hybridization. in the paper, the question of the complexity of the combinatorial part of the dna sequencing by hybridization, is analyzed. subproblems of the general problem, depending on the type of error (positive, negative), are distinguished. since decision versions of the subproblems assuming only one type of error are trivial, complexities of the search counterparts are studied. both search subproblems are proved to be strongly np-hard, as well as their uniquely promised versions.
on the presence of periodic configurations in turing machines and in counter machines. a configuration of a turing machine is given by a tape content together with a particular state of the machine. petr kůrka has conjectured that every turing machine--when seen as a dynamical system on the space of its configurations--has at least one periodic orbit. in this paper, we provide an explicit counterexample to this conjecture. we also consider counter machines and prove that, in this case, the problem of determining if a given machine has a periodic orbit in configuration space is undecidable.
structural operational semantics for weak bisimulations. in this study, we present rule formats for four main notions of bisimulation with silent moves. weak bisimulation is a congruence for any process algebra defined by wb cool rules; we have similar results for rooted weak bisimulation (milner''s ``observational equivalence''''), branching bisimulation, and rooted branching bisimulation. the theorems stating that, say, observational equivalence is an appropriate notion of equality for ccs are corollaries of the results of this paper. we also give sufficient conditions under which equational axiom systems can be generated from operational rules. indeed, many equational axiom systems appearing in the literature are instances of this general theory.
bounds and constructions for unconditionally secure distributed key distribution schemes for general access structures. in this paper we investigate the issues concerning the use of a single server across a network, the key distribution center (kdc) to enable private communications within groups of users. after providing several motivations, showing the advantages related to the distribution of the task accomplished by this server, we describe a model for such a distribution, and present bounds on the amount of resources required in a real-world implementation: random bits, memory storage, and messages to be exchanged. moreover, we introduce a linear algebraic approach to design optimal schemes distributing a kdc, and we point out that some previous constructions belong to the proposed framework.
on the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. in this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph g. this problem is known to be apx-hard, for both the edge and the vertex connectivity case. here we prove that the apx-hardness still holds even if one restricts the edge costs to an interval [1, 1 + ε], for an arbitrary small ε > 0. this result implies the first explicit lower bound on the approximability of the general version (i.e., for arbitrary graphs) of the problem. on the other hand, if the input graph satisfies the sharpened β-triangle inequality, then a (2/3 + 1/3 ċ β/1-β)-approximation algorithm is designed. this ratio tends to 1 with β tending to ½, and it improves the previous known bound of 3/2, holding for graphs satisfying the triangle inequality, as soon as β < 5/7furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of g by means of a set of edges of minimum cost is considered. this problem is known to admit a 2-approximation algorithm. here we show that whenever the input graph satisfies the sharpened β-triangle inequality with β < 2/3, then this ratio can be improved to β/1-β.
primitives for authentication in process algebras. we extend the &pgr;-calculus and the spi-calculus with two primitives that guarantee authentication. they enable us to abstract from various implementations/specifications of authentication, and to obtain idealized protocols which are "secure by construction". the main underlying idea, originally proposed in focardi (proc. sixth italian conf. on theoretical computer science, november 1998) for entity authentication, is to use the locations of processes in order to check who is sending a message (authentication of a party) and who originated a message (message authentication). the theory of local names, developed in bodei et al. (theoret. comput. sci. 253(2) (2001) 155) for the &pgr;-calculus, gives us almost for free both the partner authentication and the message authentication primitives.
tilings with trichromatic colored-edges triangles. this paper studies the tilings with colored-edges triangles constructed on a triangulation of a simply connected orientable surface such that the degree of each interior vertex is even (such as, for (fundamental) example, a part of the triangular lattice of the plane). the constraints are that we only use three colors, all the colors appear in each tile and two tile can share an edge only if this edge has the same color in both tiles.using previous results on lozenge tilings, we give a linear algorithm of coloration for triangulations of the sphere, or of planar regions with the constraint that the boundary is monochromatic.we define a flip as a shift of colors on a cycle of edges using only two colors. we prove flip connectivity of the set of solutions for the cases seen above (i.e. two tiling are mutually accessible by a sequence of flips), and prove that there is no flip accessibility in the general case where the boundary is not assumed to be monochromatic. nevertheless, using flips, we obtain a tiling invariant, even in the general case.we finish relaxing the condition, allowing monochromatic triangles. with this hypothesis, some local flips are sufficient for connectivity. we give a linear algorithm of coloration, and strong structural results on the set of solutions.
on algorithms for (, gem)-free graphs. a graph is (p5, gem)-free, when it does not contain p5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path p4) as an induced subgraph.we present o(n2) time recognition algorithms for chordal gem-free graphs and for(p5, gem)-free graphs. using a characterization of (p5, gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [a. brandstädt, d. kratsch, on the structure of (p5, gem)-free graphs, discrete appl. math. 145 (2005), 155-166], we give linear time algorithms for the following np-complete problems on (p5, gem)-free graphs: minimum coloring; maximum weight stable set; maximum weight clique; and minimum clique cover.
equitable colorings of bounded treewidth graphs. a proper coloring of a graph g is equitable if the sizes of any two color classes differ by at most one. a proper coloring is l-bounded, when each color class has size at most l. we consider the problems to determine for a given graph g (and a given integer l) whether g has an equitable (l-bounded) k-coloring. we prove that both problems can be solved in polynomial time on graphs of bounded treewidth, and show that a precolored version remains np-complete on trees.
a fully abstract model for the exchange of information in multi-agent systems. in this paper, we present a semantic theory for the exchange of information in multi-agent systems. we consider the multi-agent programming language agent communication programming language, which integrates the paradigms of concurrent constraint programming and communicating sequential processes (csp). the constraint programming techniques are used to represent and process information, whereas the synchronous communication mechanism from csp is generalised to enable the exchange of information. the semantics of the language, which is based on a generalisation of traditional failure semantics, is shown to be fully abstract with respect to observing of each terminating computation its final global store of information.
generation problems. given a fixed computable binary operation f, we study the complexity of the following generation problem: the input consists of strings a1, ..., an, b. the question is whether b is in the closure of {a1, ..., an} under operation f.for several subclasses of operations we prove tight upper and lower bounds for the generation problems. for example, we prove exponential-time upper and lower bounds for generation problems of length-monotonic polynomial-time computable operations. other bounds involve classes like np and pspace.here, the class of bivariate polynomials with positive coefficients turns out to be the most interesting class of operations. we show that many of the corresponding generation problems belong to np. however, we do not know this for all of them, e.g., for x2 + 2y this is an open question. we prove np-completeness for polynomials xaybc where a, b, c ≥ 1. also, we show np-hardness for polynomials like x2 + 2y. as a by-product we obtain np-completeness of the extended sum-of-subset problem sosc = {(w1, ..., wn, z) : ∃i ⊆ {1, ..., n}(σi∈i wic = z)} for any c ≥ 1.