waashk/dblp huggingface dataset:
relational codes of words. we consider words, i.e. strings over a finite alphabet together with a similarity relation induced by a compatibility relation on letters. this notion generalizes that of partial words. the theory of codes on combinatorics on words is revisited by defining (r,s)-codes for arbitrary similarity relations r and s. we describe an algorithm to test whether or not a finite set of words is an (r,s)-code. coding properties of finite sets of words are explored by finding maximal and minimal relations with respect to relational codes.
algorithms for terminal steiner trees. the terminal steiner tree problem (tst) consists of finding a minimum cost steiner tree where each terminal is a leaf. we describe a factor 2@r-@r/(3@r-2) approximation algorithm for the tst, where @r is the approximation factor of a given algorithm for the steiner tree problem. considering the current best value of @r, this improves a previous 3.10 factor to 2.52. for the tst restricted to instances where all edge costs are either 1 or 2, we improve the approximation factor from 1.60 to 1.42.
on the hardness of inferring phylogenies from triplet-dissimilarities. this work considers the problem of reconstructing a phylogenetic tree from triplet-dissimilarities, which are dissimilarities defined over taxon-triplets. triplet-dissimilarities are possibly the simplest generalization of pairwise dissimilarities, and were used for phylogenetic reconstructions in the past few years. we study the hardness of finding a tree best fitting a given triplet-dissimilarity table under the @?"~ norm. we show that the corresponding decision problem is np-hard and that the corresponding optimization problem cannot be approximated in polynomial time within a constant multiplicative factor smaller than 1.4. on the positive side, we present a polynomial time constant-rate approximation algorithm for this problem. we also address the issue of best-fit under maximal distortion, which corresponds to the largest ratio between matching entries in two triplet-dissimilarity tables. we show that it is np-hard to approximate the corresponding optimization problem within any constant multiplicative factor.
canonical scattered context generators of sentences with their parses. scattered context generators derive their sentences followed by the corresponding parses. this paper discusses their two canonical versions, which make this derivation either in a leftmost or rightmost way. it demonstrates that for every recursively enumerable language, l, there exists a canonical scattered context generator whose language consists of l's sentences followed by their parses. in fact, this result is established based on the generators containing no more than six nonterminals.
edge-colouring of regular graphs of large degree. we consider the following conjecture: letgbe ak-regular simple graph with an even numbernof vertices. ifk>=n/2thengisk-edge-colourable. we show that this conjecture is true for graphs that are join of two graphs and we provide a polynomial time algorithm for finding a k-edge-colouring of these graphs.
a tight analysis of the katriel-bodlaender algorithm for online topological ordering. katriel and bodlaender [irit katriel, hans l. bodlaender, online topological ordering, acm transactions on algorithms 2 (3) (2006) 364-379] modify the algorithm proposed by alpern et al. [bowen alpern, roger hoover, barry k. rosen, peter f. sweeney, f. kenneth zadeck, incremental evaluation of computational circuits, in: proceedings of the first annual acm-siam symposium on discrete algorithms (soda), 1990, pp. 32-42] for maintaining the topological order of the n nodes of a directed acyclic graph while inserting m edges and prove that their algorithm runs in o(min{m^3^/^2logn,m^3^/^2+n^2logn}) time and has an @w(m^3^/^2) lower bound. in this paper, we give a tight analysis of their algorithm by showing that it runs in time @q(m^3^/^2+mn^1^/^2logn).
learning languages from positive data and a limited number of short counterexamples. we consider two variants of a model for learning languages in the limit from positive data and a limited number of short negative counterexamples (counterexamples are considered to be short if they are smaller than the largest element of input seen so far). negative counterexamples to a conjecture are examples which belong to the conjectured language but do not belong to the input language. within this framework, we explore how/when learners using n short (arbitrary) negative counterexamples can be simulated (or simulate) using least short counterexamples or just 'no' answers from a teacher. we also study how a limited number of short counterexamples fairs against unconstrained counterexamples, and also compare their capabilities with the data that can be obtained from subset, superset, and equivalence queries (possibly with counterexamples). a surprising result is that just one short counterexample can sometimes be more useful than any bounded number of counterexamples of arbitrary sizes. most of the results exhibit salient examples of languages learnable or not learnable within corresponding variants of our models.
on a class of infinite words with affine factor complexity. in this article, we consider the fixed point of a primitive substitution canonically defined by a @b-numeration system. the problem of determination of the factor complexity of such an infinite word has been solved only partially. here we provide a necessary and sufficient condition on the renyi expansion of one for having an affine factor complexity map c(n), that is, such that c(n)=an+b for any positive integer n.
on clique separators, nearly chordal graphs, and the maximum weight stable set problem. clique separators in graphs are a helpful tool used by tarjan as a divide-and-conquer approach for solving various graph problems such as the maximum weight stable set (mws) problem, maximum clique, graph coloring and minimum fill-in, but few examples of graph classes having clique separators are known. we use this method to solve mws in polynomial time for two classes where the unweighted maximum stable set (ms) problem is solvable in polynomial time by augmenting techniques but the complexity of the mws problem was open. another example, namely a result by alekseev for the mws problem on a subclass of p"5-free graphs obtained by clique separators, can be improved by our techniques. we also combine clique separators with decomposition by homogeneous sets in graphs and use the following notion: a graph is nearly@p if for each of its vertices, the subgraph induced by the set of its nonneighbors has property @p. we deal with the cases @p@?{chordal,perfect}. this also simplifies a result obtained by a method called struction.
the affix array data structure and its applications to rna secondary structure analysis. efficient string-processing in large data sets like complete genomes is strongly connected to the suffix tree and similar index data structures. with respect to complex structural string analysis like the search for rna secondary structure patterns, unidirectional suffix tree algorithms are inferior to bidirectional algorithms based on the affix tree data structure. the affix tree incorporates the suffix tree and the suffix tree of the reverse text in one tree structure but suffers from its large memory requirements. in this paper i present a new data structure, denoted affix array, which is equivalent to the affix tree with respect to its algorithmic functionality, but with smaller memory requirements and improved performance. i will show a linear time construction of the affix array without making use of the linear time construction of the affix tree. i will also show how bidirectional affix tree traversals can be transferred to the affix array and present the impressive results of large scale rna secondary structure analysis based on the new data structure.
freeness of partial words. the paper approaches the classical combinatorial problem of freeness of words, in the more general case of partial words. first, we propose an algorithm that tests efficiently whether a partial word is k-free or not, for a given k. then, we show that there exist arbitrarily many k-free infinite partial words, over a binary alphabet, containing an infinite number of holes, for k>=3. moreover, we present an efficient algorithm for the construction of a cube-free partial word with a given number of holes, over a binary alphabet. in the final section of the paper, we show that there exists an infinite word, over a four-symbol alphabet, in which we can substitute randomly one symbol with a hole, and still obtain a cube-free word; we show that such a word does not exist for alphabets with fewer symbols. further, we prove that in this word we can replace arbitrarily many symbols with holes, such that each two consecutive holes are separated by at least two symbols, and obtain a cube-free partial word. this result seems interesting because any partial word containing two holes with less than two symbols between them is not cube-free. finally, we modify the previously presented algorithm to construct, over a four-symbol alphabet, a cube-free partial word with exactly n holes, having minimal length, among all the possible cube-free partial words with at least n holes.
reducing rank-maximal to maximum weight matching. given a bipartite graph g(v,e), v=a@?@?b where |v|=n,|e|=m and a partition of the edge set into r@?m disjoint subsets e=e"1@?@?e"2@?@?...@?@?e"r, which are called ranks, the rank-maximal matching problem is to find a matching m of g such that |m@?e"1| is maximized and given that |m@?e"1| is maximized, |m@?e"2| is also maximized, and so on. such a problem arises as an optimization criteria over a possible assignment of a set of applicants to a set of posts. the matching represents the assignment and the ranks on the edges correspond to a ranking of the posts submitted by the applicants. the rank-maximal matching problem and several other optimization variants, e.g. fair matching and maximum cardinality rank-maximal matching, can be solved by a reduction to the weight matching problem in time o(rnmlogn). recently, irving et al. developed a combinatorial approach which improves the running time for the rank-maximal matching problem to o(min(n+r,rn)m). they raised the open questions on (a) whether such a running time can be achieved by the weight matching reduction and (b) whether such a running time can be achieved for the other variants of the problem. in this work we show how the reduction to the weight matching problem can also be used to achieve the same running time. our algorithm is simpler and more intuitive.
on the hardness of minimizing space for all-shortest-path interval routing schemes. k-interval routing scheme (k-irs) is a compact routing method that allows up to k interval labels to be assigned to an arc; and global k-irs allows not more than a total of k interval labels in the whole network. a fundamental problem is to characterize the networks that admit k-irs (or global k-irs). many of the problems related to single-shortest-path k-irs have already been shown to be np-complete. for all-shortest-path k-irs, the characterization problem remains open for k>=1. in this paper, we study the time complexity of devising minimal-space all-shortest-path k-irss and show that it is np-complete to decide whether a graph admits an all-shortest-path k-irs, for every integer k>=3, and so is that of deciding whether a graph admits an all-shortest-path k-strict irs, for every integer k>=4. these are the first np-completeness results for all-shortest-path k-irs where k is a constant and the graph is unweighted. the np-completeness holds also for the linear case. we also prove that it is np-complete to decide whether an unweighted graph admits an all-shortest-path irs with global compactness of at most k, which also holds for the linear and strict cases.
triangulating a convex polygon with fewer number of non-standard bars. for a given convex polygon with inner angle no less than 23@p and boundary edge bounded by [l,@al] for 1@?@a@?1.4, where l is a given standard bar's length, we investigate the problem of triangulating the polygon using some steiner points such that (i) the length of each edge in triangulation is bounded by [@bl,2l], where @b is a given constant and meets 0
prefix-free regular languages and pattern matching. we explore the regular-expression matching problem with respect to prefix-freeness of the pattern. we prove that a prefix-free regular expression gives only a linear number of matching substrings in the size of a given text. based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.
tag systems and collatz-like functions. tag systems were invented by emil leon post and proven recursively unsolvable by marvin minsky. these production systems have proved to be very useful in constructing small universal (turing complete) systems for several different classes of computational systems, including turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both the shift number v and the number of symbols @m. this paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. the main result is the reduction of the 3n+1-problem to a surprisingly small tag system. it indicates that the present unsolvability line-defined in terms of @m and v-for tag systems might be significantly decreased.
an improved approximation algorithm for capacitated multicast routings in networks. let g=(v,e) be a connected graph such that each edge e@?e is weighted by nonnegative real w(e). let s be a vertex designated as a source, k be a positive integer, and s@?v be a set of terminals. the capacitated multicast tree routing problem (cmtr) asks to find a partition {z"1,z"2,...,z"@?} of s and a set {t"1,t"2,...,t"@?} of trees of g such that z"i consists of at most k terminals and each t"i spans z"i@?{s}. the objective is to minimize @?"i"="1^@?w(t"i), where w(t"i) denotes the sum of weights of all edges in t"i. in this paper, we propose a (3/2+(4/3)@r)-approximation algorithm to the cmtr, where @r is the best achievable approximation ratio for the steiner tree problem.
true-concurrency probabilistic models: markov nets and a law of large numbers. we introduce the model of markov nets, a probabilistic extension of safe petri nets under the true-concurrency semantics-this means that traces, not firing sequences, are given a probability. this model builds upon our previous work on probabilistic event structures. we use the notion of a branching cell for event structures, and show that the latter provides an adequate conception of local state for nets. we prove a law of large numbers (lln) for markov nets, which constitutes the main contribution of the paper. this lln allows for the characterization, in a quantitative way, of the asymptotic behavior of markov nets.
online bin packing with arbitrary release times. we study a new variant of the online bin-packing problem, in which each item a"i is associated with a size a"i and also a release time r"i so that it must be placed at least r"i above the bottom of a bin. items arrive in turn and must be assigned without any knowledge of subsequent items. the goal is to pack all items into unit-size bins using the minimum number of bins. we study the problem with all items have equal size. first, we show that the any fit algorithm cannot be approximated within any constant. then we present a best possible online algorithm with asymptotic competitive ratio of two.
a rounding algorithm for approximating minimum manhattan networks. for a set t of n points (terminals) in the plane, a manhattan network on t is a network n(t)=(v,e) with the property that its edges are horizontal or vertical segments connecting points in v@?t and for every pair of terminals, the network n(t) contains a shortest l"1-path between them. a minimum manhattan network on t is a manhattan network of minimum possible length. the problem of finding minimum manhattan networks has been introduced by gudmundsson, levcopoulos, and narasimhan [j. gudmundsson, c. levcopoulos, g. narasimhan, approximating a minimum manhattan network, nordic journal of computing 8 (2001) 219-232. proc. approx'99, 1999, pp. 28-37] and its complexity status is unknown. several approximation algorithms (with factors 8, 4, and 3) have been proposed; recently kato, imai, and asano [r. kato, k. imai, t. asano, an improved algorithm for the minimum manhattan network problem, isaac'02, in: lncs, vol. 2518, 2002, pp. 344-356] have given a factor 2-approximation algorithm, however their correctness proof is incomplete. in this paper, we propose a rounding 2-approximation algorithm based on an lp-formulation of the minimum manhattan network problem.
motif patterns in 2d. motif patterns consisting of sequences of intermixed solid and don't-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. in order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. in this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. the remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms.
third-order idealized algol with iteration is decidable. the problems of contextual equivalence and approximation are studied for the third-order fragment of idealized algol with iteration (ia"3^*). they are approached via a combination of game semantics and language theory. it is shown that for each ia"3^*-term one can construct a pushdown automaton recognizing a representation of the strategy induced by the term. the automata have some additional properties ensuring that the associated equivalence and inclusion problems are solvable in ptime. this gives an exptime decision procedure for the problems of contextual equivalence and approximation for @b-normal terms. exptime-hardness of the problems, even for terms without iteration, is also shown.
expressivity of coalgebraic modal logic: the limits and beyond. modal logic has a good claim to being the logic of choice for describing the reactive behaviour of systems modelled as coalgebras. logics with modal operators obtained from so-called predicate liftings have been shown to be invariant under behavioural equivalence. expressivity results stating that, conversely, logically indistinguishable states are behaviourally equivalent depend on the existence of separating sets of predicate liftings for the signature functor at hand. here, we provide a classification result for predicate liftings which leads to an easy criterion for the existence of such separating sets, and we give simple examples of functors that fail to admit expressive normal or monotone modal logics, respectively, or in fact an expressive (unary) modal logic at all. we then move on to polyadic modal logic, where modal operators may take more than one argument formula. we show that every accessible functor admits an expressive polyadic modal logic. moreover, expressive polyadic modal logics are, unlike unary modal logics, compositional.
optimal reachability for multi-priced timed automata. in this paper, we prove the decidability of the minimal and maximal reachability problems for multi-priced timed automata, an extension of timed automata with multiple cost variables evolving according to given rates for each location. more precisely, we consider the problems of synthesizing the minimal and maximal costs of reaching a given target location. these problems generalize conditional optimal reachability, i.e., the problem of minimizing one primary cost under individual upper bound constraints on the remaining, secondary, costs, and the problem of maximizing the primary cost under individual lower bound constraints on the secondary costs. furthermore, under the liveness constraint that all traces eventually reach the goal location, we can synthesize all costs combinations that can reach the goal. the decidability of the minimal reachability problem is proven by constructing a zone-based algorithm that always terminates while synthesizing the optimal cost tuples. for the corresponding maximization problem, we construct two zone-based algorithms, one with and one without the above liveness constraint. all algorithms are presented in the setting of two cost variables and then lifted to an arbitrary number of cost variables.
panconnectivity and edge-pancyclicity of faulty recursive circulant g(2, 4). in this paper, we investigate a problem on embedding paths into recursive circulant g(2^m,4) with faulty elements (vertices and/or edges) and show that each pair of vertices in recursive circulant g(2^m,4), m>=3, are joined by a fault-free path of every length from m+1 to |v(g(2^m,4)@?f)|-1 inclusive for any fault set f with |f|@?m-3. the bound m-3 on the number of acceptable faulty elements is the maximum possible. moreover, recursive circulant g(2^m,4) has a fault-free cycle of every length from 4 to |v(g(2^m,4)@?f)| inclusive excluding 5 passing through an arbitrary fault-free edge for any fault set f with |f|@?m-3.
algorithmic analysis of polygonal hybrid systems, part ii: phase portrait and tools. polygonal differential inclusion systems (spdi) are a subclass of planar hybrid automata which can be represented by piecewise constant differential inclusions. the reachability problem as well as the computation of certain objects of the phase portrait is decidable. in this paper we show how to compute the viability, controllability and invariance kernels, as well as semi-separatrix curves for spdis. we also present the tool speedi^+, which implements a reachability algorithm and computes phase portraits of spdis.
gathering asynchronous oblivious mobile robots in a ring. we consider the problem of gathering identical, memoryless, mobile robots in one node of an anonymous unoriented ring. robots start from different nodes of the ring. they operate in look-compute-move cycles and have to end up in the same node. in one cycle, a robot takes a snapshot of the current configuration (look), makes a decision to stay idle or to move to one of its adjacent nodes (compute), and in the latter case makes an instantaneous move to this neighbor (move). cycles are performed asynchronously for each robot. for an odd number of robots we prove that gathering is feasible if and only if the initial configuration is not periodic, and we provide a gathering algorithm for any such configuration. for an even number of robots we decide the feasibility of gathering except for one type of symmetric initial configurations, and provide gathering algorithms for initial configurations proved to be gatherable.
parikh matrices and amiable words. using the fact that the parikh matrix mapping is not an injective mapping, the paper investigates some properties of the set of words with the same parikh matrix; these words are called ''amiable''. the presented results extend the results obtained in [a. atanasiu, binary amiable words, int. j. found. comput. sci. 18 (2) (2007) 387-400] for the binary case. in particular it is shown that all the words having the same parikh matrix can be obtained one from another by applying only two types of transformations. moreover, the mirrors of two amiable words are also amiable (thus forming a symmetrical class of words).