waashk/dblp huggingface dataset:
a computational model for rna multiple structural alignment. this paper addresses the problem of aligning multiple sequences of noncoding rna (ncrna) genes. we approach this problem with the biologically motivated paradigm that scoring of ncrna alignments should be based primarily on secondary structure rather than nucleotide conservation. we introduce a novel graph theoretic model (nlg) for analyzing algorithms based on this approach, prove that the rna multiple alignment problem is np-complete in this model, and present a polynomial time algorithm that approximates the optimal structure of size s within a factor of o(log^2s).
a logical approach to stable domains. building on earlier work by guo-qiang zhang on disjunctive information systems, and by thomas ehrhard, pasquale malacaria, and the first author on stable stone duality, we develop a framework of disjunctive propositional logic in which theories correspond to algebraic l-domains. disjunctions in the logic can be indexed by arbitrary sets (as in geometric logic) but must be provably disjoint. this raises several technical issues which have to be addressed before clean notions of axiom system and theory can be defined. we show soundness and completeness of the proof system with respect to distributive disjunctive semilattices, and prove that every such semilattice arises as the lindenbaum algebra of a disjunctive theory. via stable stone duality, we show how to use disjunctive propositional logic for a logical description of algebraic l-domains.
generalized ultrametric spaces in quantitative domain theory. domains and metric spaces are two central tools for the study of denotational semantics in computer science, but are otherwise very different in many fundamental aspects. a construction that tries to establish links between both paradigms is the space of formal balls, a continuous poset which can be defined for every metric space and that reflects many of its properties. on the other hand, in order to obtain a broader framework for applications and possible connections to domain theory, generalized ultrametric spaces (gums) have been introduced. in this paper, we employ the space of formal balls as a tool for studying these more general metrics by using concepts and results from domain theory. it turns out that many properties of the metric can be characterized via its formal-ball space. furthermore, we can state new results on the topology of gums as well as two new fixed point theorems, which may be compared to the priesz-crampe and ribenboim theorem, and the banach fixed point theorem, respectively. deeper insights into the nature of formal-ball spaces are gained by applying methods from category theory. our results suggest that, while being a useful tool for the study of gums, the space of formal balls does not provide the hoped-for general connection to domain theory.
faster two-dimensional pattern matching with rotations. the most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of o(n^2m^3), where the size of the text is nxn and the size of the pattern is mxm. in this paper we present a new algorithm for the problem whose running time is o(n^2m^2).
invariance under stuttering in a temporal logic of actions. we show that some simple and useful stutter-invariant properties definable in the language of lamport's simple temporal logic of actions (stla) are not definable in stla and present a natural extension of stla that allows one to express all stutter-invariant properties definable in the language of stla.
complexity and approximability of k-splittable flows. let g = (v, e) be a graph with a source node s and a sink node t, |v| = n, |e| = m. for a given number k, the maximum k-splittable flow problem (mksf) is to find an s, t-flow of maximum value with a flow decomposition using at most k paths. in the multicommodity case this problem generalizes disjoint paths problems and unsplittable flow problems. we provide a comprehensive overview of the complexity and approximability landscape of mksf on directed and undirected graphs. we consider constant values of k and k depending on graph parameters. for arbitrary constant values of k, we prove that the problem is strongly np-hard on directed and undirected graphs already for k = 2. this extends a known np-hardness result for directed graphs that could not be applied to undirected graphs. furthermore, we show that mksf cannot be approximated with a performance ratio better than 5/6. this is the first constant bound given for arbitrary constant values of k. for non-constant values of k, the polynomial solvability was known before for all k ≥ m, but open for smaller k. we prove that mksf is np-hard for all k fulfilling 2 ≤ k ≤ m - n + 1 (for n ≥ 3). for all other values of k the problem is shown to be polynomially solvable.
dynamic load balancing with group communication. this work considers the problem of efficiently performing a set of tasks using a network of processors in the setting where the network is subject to dynamic reconfigurations, including partitions and merges. a key challenge for this setting is the implementation of dynamic load balancing that reduces the number of tasks that are performed redundantly because of the reconfigurations. we explore new approaches for load balancing in dynamic networks that can be employed by applications using a group communication service (gcs). the gcs that we consider include a membership service (establishing new groups to reflect dynamic changes) but does not include maintenance of a primary component. for the n-processor, n-task load balancing problem defined in this work, the following specific results are obtained. for the case of fully dynamic changes including fragmentation and merges we show that the termination time of any on-line task assignment algorithm is greater than the termination time of an off-line task assignment algorithm by a factor greater than n/12. we present a load balancing algorithm that guarantees completion of all tasks in all fragments caused by partitions with work o(n + f ċ n) in the presence of f fragmentation failures. we develop an effective scheduling strategy for minimizing the task execution redundancy and we prove that our strategy provides each of the n processors with a schedule of θ(n1/3) tasks such that at most one task is performed redundantly by any two processors.
reasoning under minimal upper bounds in propositional logic. reasoning from the minimal models of a theory, as fostered by circumscription, is in the area of artificial intelligence an important method to formalize common sense reasoning. however, as it appears, minimal models may not always be suitable to capture the intuitive semantics of a knowledge base, aiming intuitively at an exclusive interpretation of disjunctions of atoms, i.e., if possible then assign at most one of the disjuncts the value true in a model. in this paper, we consider an approach which is more lenient and also admits non-minimal models, such that inclusive interpretation of disjunction also may be possible in cases where minimal model reasoning adopts an exclusive interpretation. nonetheless, in the spirit of minimization, the approach aims at including only positive information that is necessary. this is achieved by closing the set of admissible models of a theory under minimal upper bounds in the set of models of the theory, which we refer to as curbing. we demonstrate this method on some examples, and investigate its semantical and computational properties. we establish that curbing is an expressive reasoning method, since the main reasoning tasks are shown to be pspace-complete. on the other hand, we also present cases of lower complexity, and in particular cases in which the complexity is located, just as for ordinary minimal model reasoning, at the second level of the polynomial hierarchy, or even below.
coding with variable block maps. in this article we study a special class of sliding block maps that we call variable block maps. we characterize the subsets of finite and infinite sequences that can be obtained as the image of another subset of symbolic sequences by a variable block map. on the other way, we show that the coding process induced by such kind of block maps can be reversed, even with partial knowledge about the variable block maps, and we give an explicit construction of a canonical antecedent.
visual cryptography schemes with optimal pixel expansion. a visual cryptography scheme encodes a black and white secret image into n shadow images called shares which are distributed to the n participants. such shares are such that only qualified subsets of participants can "visually" recover the secret image. usually, the reconstructed image will be darker than the background of the image itself. in this paper we consider visual cryptography schemes satisfying the model introduced by tzeng and hu [a new approach for visual cryptography, designs, codes and cryptography 27 (3) (2002) 207-227]. in such a model, the recovered secret image can be darker or lighter than the background. we prove a lower bound on the pixel expansion of the scheme and, for (2, n)-threshold visual cryptography schemes, we provide schemes achieving the bound. our schemes improve on the ones proposed by tzeng and hu.
two algebraic approaches to variants of the concatenation product. we extend an existing approach of the bideterministic concatenation product of languages aiming at the study of three other variants: unambiguous, left deterministic and right deterministic. such an approach is based on monoid expansions. the proofs are purely algebraic and use another approach, based on properties on the kernel category of a monoid relational morphism, without going through the languages. this gives a unified fashion to deal with all these variants and allows us to better understand the connections between these two approaches. finally, we show that local finiteness of an m-variety is transferred to the m-varieties corresponding to these variants and apply the general results to the m-variety of idempotent and commutative monoids.
degrees of non-monotonicity for restarting automata. in the literature various notions of monotonicity for restarting automata have been studied. here we introduce two new variants of monotonicity for restarting automata and for two-way restarting automata: left-monotonicity and right-left-monotonicity. it is shown that for the various types of deterministic and nondeterministic (two-way) restarting automata without auxiliary symbols, these notions yield infinite hierarchies, and we compare these hierarchies to each other. further, as a tool used to simplify some of the proofs, the shrinking restarting automaton is introduced, which is a generalization of the standard (length-reducing) restarting automaton to the weight-reducing case. some of the consequences of this generalization are also discussed.
an algorithmic approach to the problem of a semiretract base. a semiretract of a free monoid a* is an intersection of a family of retracts of a* and it is a free submonoid. in the paper we propose an algorithmic approach to the problem of finding the base (code) of a semiretract.
the degree distribution of the generalized duplication model. we study and generalize the duplication model of pastor-satorras et al. [evolving protein interaction networks through gene duplication, j. theor. biol. 222 (2003) 199-210]. this model generates a graph by iteratively "duplicating" a randomly chosen node as follows: we start at t0 with a fixed graph g(t0) of size t0. at each step t > t0 a new node vt is added. the node vt selects an existing node u from v(g(t - 1)) = {v1,...,vt-1} uniformly at random (uar). the node vt then connects to each neighbor of the node u in g(t - 1) independently with probability p. additionally, vt connects uar to every node of v(g(t - 1)) independently with probability r/t, and parallel edges are merged. unlike other copy-based models, the degree of the node vt in this model is not fixed in advance; rather it depends strongly on the degree of the original node u it selected. our main contributions are as follows: we show that (1) the duplication model of pastor-satorras et al. does not generate a truncated power-law degree distribution as stated in pastor-satorras et al. [evolving protein interaction networks through gene duplication, j. theor. biol. 222 (2003) 199-210]. (2) the special case where r = 0 does not give a power-law degree distribution as stated in chung et al. [duplication models for biological networks, j. comput. biol. 10 (2003) 677-687]. (3) we generalize the pastor-satorras et al. duplication process to ensure (if required) that the minimum degree of all vertices is positive. we prove that this generalized model has a power-law degree distribution.
a network flow approach to the minimum common integer partition problem. in the k-minimum common integer partition problem, abbreviated as k-mcie we are given k multisets x1,...,xk of positive integers, the goal is to find an integer multiset t of the minimum size such that for every i, we can partition each of the integers in xi so that the disjoint (multiset) union of their partitions equals t. this problem has applications in computational molecular biology, in particular, ortholog assignment and dna hybridization fingerprint assembly. the problem is known to be np-hard for any k ≥ 2. in this article, we improve the approximation ratio for k-mcip by viewing this problem as a flow decomposition problem in some flow network. we show an efficient 0.5625k-approximation algorithm, improving upon the previously best known 0.6139k-approximation algorithm for this problem.
a note on ambiguity of internal contextual grammars. in this paper, we continue the study of ambiguity of internal contextual grammars which was investigated in ilie [on ambiguity in internal contextual languages, in: c. martin-vide (ed.), second int. conf. on mathematical linguistics, tarragona, 1996, john benjamins, amsterdam, 1997, pp. 29-45] and martin-vide et al. [attempting to define the ambiguity in internal contextual languages, in: c. martin-vide (ed.), second int. conf. on mathematical linguistics, tarragona, 1996, john benjamins, amsterdam, 1997, pp. 59-81]. we solve some open problems formulated in these papers. the main results are: (i) there are inherently 1-ambiguous languages with respect to internal contextual grammars with arbitrary choice which are 0-unambiguous with respect to finite choice, (ii) there are inherently 2-ambiguous languages with respect to internal contextual grammars with arbitrary choice which are 1-unambiguous with respect to regular choice, and (iii) there are inherently 2-ambiguous languages with respect to depth-first internal contextual grammars with arbitrary choice which are 1-unambiguous with respect to finite choice.
iterated sequential transducers as language generating devices. iterated finite state sequential transducers are considered as language generating devices. the hierarchy induced by the size of the state alphabet is proved to collapse to the fourth level. the corresponding language families are related to the families of languages generated by lindenmayer systems and chomsky grammars. finally, some results on deterministic and extended iterated finite state transducers are established.
edge-bandwidth of grids and tori. the edge-bandwidth of a graph g is the smallest number b' for which there is a bijective labeling of e(g) with {1,...,e(g)} such that the difference between the labels at any adjacent edges is at most b'. here we compute the edge-bandwidth for rectangular grids: b'(pm⊕pn)=2 min(m,n) - 1 if max(m,n) ≥ 3, where ⊕ is the cartesian product and pn denotes the path on n vertices. this settles a conjecture of calamoneri et al. [new results on edge-bandwidth, theoret. comput. sci. 307 (2003) 503-513]. we also compute the edge-bandwidth of any torus (a product of two cycles) within an additive error of 5.
on a question of leiss regarding the hanoi tower problem. the tower of hanoi problem is generalized in such a way that the pegs are located at the vertices of a directed graph g, and moves of disks may be made only along edges of g. leiss obtained a complete characterization of graphs in which arbitrarily many disks can be moved from the source vertex s to the destination vertex d. here we consider graphs which do not satisfy this characterization; hence, there is a bound on the number of disks which can be handled. denote by gn the maximal such number as g varies over all such graphs with n vertices and s, d vary over the vertices. answering a question of leiss [finite hanoi problems: how many discs can be handled? congr. numer. 44 (1984) 221-229], we prove that gn grows sub-exponentially fast. moreover, there exists a constant c such that gn ≤ cn1/2 log2n for each n. on the other hand, for each ε > 0 there exists a constant cε > 0 such that gn ≥ cεn(1/2-ε)log2n for each n.
cost distribution of the chang-roberts leader election algorithm and related problems. a detailed probabilistic analysis is proposed of the total number of messages of the chang-roberts leader election algorithm. the cost is shown to be closely related to the total path length in random recursive trees, the total left-path length in increasing binary trees and the major cost of an in situ permutation algorithm.
constructive root bound for k-ary rational input numbers. guaranteeing accuracy is the critical capability in exact geometric computation, an important paradigm for constructing robust geometric algorithms. constructive root bounds is the fundamental technique needed to achieve such guaranteed accuracy. current bounds are overly pessimistic in the presence of general rational input numbers. in this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. since a majority of input numbers in scientific and engineering applications are either binary (k = 2) or decimal (k = 10), our results could lead to a significant speedup for a large class of applications. we apply our method to two of the best available constructive root bounds, the bfmss bound and the degree-measure bound. implementation and experimental results based on the core library are reported.
truthful algorithms for scheduling selfish tasks on parallel machines. we consider the problem of designing truthful mechanisms for scheduling selfish tasks (or agents)--whose objective is the minimization of their completion times--on parallel identical machines in order to minimize the makespan. a truthful mechanism can be easily obtained in this context (if we, of course, assume that the tasks cannot shrink their lengths) by scheduling the tasks following the increasing order of their lengths. the quality of a mechanism is measured by its approximation factor (price of anarchy, in a distributed system) w.r.t. the social optimum. the previous mechanism, known as spt, produces a (2 - 1/m)-approximate schedule, where m is the number of machines. the central question in this paper is the following: "are there other truthful mechanisms with better approximation guarantee (price of anarchy) for the considered scheduling problem?" this question has been raised by christodoulou et al. [coordination mechanisms, in: proc. of icalp 2004, lecture notes in computer science, vol. 3142, 345-357.] in the context of coordination mechanisms, but it is also relevant in centrally controlled systems. we present (randomized) truthful mechanisms for both the centralized and the distributed settings that improve the (expected) approximation guarantee (price of anarchy) of the spt mechanism. our centralized mechanism holds for any number of machines and arbitrary task lengths, while the coordination mechanism holds only for two machines and task lengths that are powers of a certain constant.
a fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date. we develop a fully polynomial-time approximation scheme (fptas) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. the fptas is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.
scheduling resource allocation with timeslot penalty for changeover. given a time slotted list of resource capacities, we address the problem of scheduling resource allocation considering that a change in allocation results in the changeover penalty of one timeslot. the goal is to maximize the overall allocation of resources. we prove that no 1-lookahead algorithm can be better than 8/5-competitive. we provide improved analysis of wait dominate hold (wdh) algorithm that was previously known to be 4-competitive. we prove that wdh is 8/3-competitive. we also consider k-lookahead algorithms, and prove lower bound of (k + 2)/(k + 1) on their competitiveness and give an online algorithm that is 2-competitive.
list edge and list total colorings of planar graphs without 4-cycles. let g be a planar graph with maximum degree δ such that g has no cycle of length from 4 to k, where k ≥ 4. then the list chromatic index χ′1(g) = δ and the list total chromatic number χ″1(g) = δ + 1 if (δ, k) ∈ {(7, 4), (6, 5), (5, 8)}. furthermore, χ′1(g) = δ if (δ, k) ∈ {(4, 14)}.
on the edge l radius of saitou and nei's method for phylogenetic reconstruction. in this paper, we study the performance of saitou and nei's neighbor-joining method for phylogenetic reconstruction. we show that the edge l∞ radius of the method is 1/4. this improves an result by atteson [the performance of neighbor-joining methods of phylogenetic reconstruction, algorithmica 25 (1999) 251-278] and xu et al. [a lower bound on the edge l∞ radius of saitou and nei's method for phylogenetic reconstruction, inform. process. lett. 94(5) (2005) 225-230]. previously, only an upper bound 1/4 and a lower bound 1/6 were known.
efficient sample sort and the average case analysis of pesort. the purpose of the paper is twofold. first, we want to search for a more efficient sample sort. secondly, by analyzing a variant of samplesort, we want to settle an open problem: the average case analysis of proportion extend sort (pesort for short). an efficient variant of samplesort given in the paper is called full sample sort. this algorithm is simple. it has a shorter object code and is almost as fast as pesort. theoretically, we show that full sample sort with a linear sampling size performs at most n log n = o(n) comparisons and o(n log n) exchanges on the average, but o(n log2 n) comparisons in the worst case. this is an improvement on the original samplesort by frazer and mckellar, which requires n log n + o(n log log n) comparisons on the average and o(n2) comparisons in the worst case. on the other hand, we use the same analyzing approach to show that pesort, with any p > 0, performs also at most n log n + o(n) comparisons on the average. notice, cole and kandathil analyzed only the case p = 1 of pesort. for any p > 0, they did not. namely, their approach is suitable only for a special case such as p = 1, while our approach is suitable for the generalized case.