waashk/dblp huggingface dataset:
a quadratic identity for the number of perfect matchings of plane graphs. we present a quadratic identity on the number of perfect matchings of plane graphs by the method of graphical condensation, which generalizes the results found by propp [j. propp, generalized domino-shuffling, theoret. comput. sci. 303 (2003) 267-301], kuo [e.h. kuo, applications of graphical condensation for enumerating matchings and tilings, theoret. comput. sci. 319 (2004) 29-57], and yan, yeh, and zhang [w.g. yan, y.-n. yeh, f.j. zhang, graphical condensation of plane graphs: a combinatorial approach, theoret. comput. sci. 349 (2005) 452-461].
long binary patterns are abelian 2-avoidable. we show that every long binary pattern is abelian 2-avoidable.
minimum-cost delegation in service composition. the paradigm of automated service composition through the integration of existing services promises a fast and efficient development of new services in cooperative service (e.g., business) environments. although the ''why'' part of this paradigm is well understood, many key pieces are missing to utilize the available opportunities. recently ''service communities'' where service providers with similar interests can register their services are proposed toward realizing this goal. in these communities, requests for services posed by users can be processed by delegating them to existing services, and orchestrating their executions. we use a service framework similar to the ''roman'' model departing from it particularly assuming service requirements are specified in a sequence form. we also extend the framework to integrate activity processing costs into the delegation computation and to have services with bounded storage as opposed to finite storage. we investigate the problem of efficient processing of service requests in service communities and develop polynomial time delegation techniques guaranteeing optimality.
a palindromization map for the free group. we define a self-map pal:f"2->f"2 of the free group on two generators a,b, using automorphisms of f"2 that form a group isomorphic to the braid group b"3. the map pal restricts to de luca's right iterated palindromic closure on the submonoid generated by a,b. we show that pal is continuous for the profinite topology on f"2; it is the unique continuous extension of de luca's right iterated palindromic closure to f"2. the values of pal are palindromes and coincide with the elements g@?f"2 such that abg and bag are conjugate.
deadline guaranteed packet scheduling for overloaded traffic in input-queued switches. many applications need to solve the deadline guaranteed packet scheduling problem. however, it is a very difficult problem if three or more deadlines are present in a set of packets to be scheduled. the traditional approach to dealing with this problem is to use edf (earliest deadline first) or similar methods. recently, a non-edf based algorithm was proposed that constantly produces a higher throughput than edf-based algorithms by repeatedly finding an optimal scheduling for two classes. however, this new method requires the two classes be non-overloaded, which greatly restricts its applications. since the overloaded situation is not avoidable from one iteration to the next in dealing with multiple classes, it is compelling to answer the open question: can we find an optimal schedule for two overloaded classes efficiently? this paper first proves that this problem is np-complete. then, this paper proposes an optimal preprocessing algorithm that guarantees to drop a minimum number of packets from the two classes such that the remaining set is non-overloaded. this result directly improves on the new method.
strategic attack on the shrinking generator. the shrinking generator is a simple keystream generator with applications in stream ciphers, which is still considered as a secure generator. this work shows that, in order to cryptanalyze it, fewer intercepted bits than indicated by the linear complexity are necessary. indeed, whereas the linear complexity of shrunken sequences is between a@?2^(^s^-^2^) and a@?2^(^s^-^1^), we claim that the initial states of both component registers are easily computed with fewer than a@?s shrunken bits located at particular positions. such a result is proven thanks to the definition of shrunken sequences as interleaved sequences. consequently, it is conjectured that this statement can be extended to all interleaved sequences. furthermore, this paper confirms that certain bits of the interleaved sequences have a greater strategic importance than others, which must be considered as a proof of weakness of interleaved generators.
sequential vector packing. we introduce a novel variant of the well known d-dimensional bin (or vector) packing problem. given a sequence of non-negative d-dimensional vectors, the goal is to pack these into as few bins as possible, of the smallest possible size. in the classical problem, the bin size vector is given and the sequence can be partitioned arbitrarily. we study a variation where the vectors have to be packed in the order in which they arrive, and the bin size vector can be chosen once in the beginning. this setting gives rise to two combinatorial problems: one in which we want to minimize the number of bins used for a given total bin size, and one in which we want to minimize the total bin size for a given number of bins. we prove that both problems are np-hard, and propose an lp based bicriteria (1@e,11-@e)-approximation algorithm. we give a 2-approximation algorithm for the version with a bounded number of bins. furthermore, we investigate properties of natural greedy algorithms, and present an easy to implement heuristic, which is fast and performs well in practice. experiments with the heuristic and an ilp formulation yield promising results on real world data.
generating all permutations by context-free grammars in greibach normal form. we consider context-free grammars g"n in greibach normal form and, particularly, in greibach m-form (m=1,2) which generates the finite language l"n of all n! strings that are permutations of n different symbols (n>=1). these grammars are investigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols and the number of production rules of g"n as functions of n. as in the case of chomsky normal form, these descriptional complexity measures grow faster than any polynomial function.
complexity of question/answer games. question/answer games (q/a games for short) are a generalization of the renyi-ulam game and they are a model for information extraction in parallel. a q/a game, g=(d,s,(q"1,...,q"k)), is played on a directed acyclic graph, d=(v,e), with a distinguished start vertex s. in the ith round, paul selects a set, q"i@?v, of at most q"i non-terminal vertices. carole responds by choosing an outgoing edge from each vertex in q"i. at the end of k rounds, paul wins if carole's answers define a unique path from the root to one of the terminal vertices in d. in this paper we analyze the complexity of q/a games and explore the notion of fixed strategies. we show that the problem of determining if paul wins the game played on a rooted tree via a fixed strategy is in np. the same problem is @s"2p-complete for arbitrary digraphs. for general strategies, the problem is np-complete if we restrict a two-round game to a digraph of depth three. an interesting aspect of this game is that it captures the even levels of the polynomial-time hierarchy when restricted to a fixed number of rounds; that is, determining if paul wins a k-round game is @s"2"k"-"2p-complete. the general version of the game is known to be pspace-complete [s. abbasi, n. sheikh, some hardness results for q/a games, integers 7 (2007) g08]. in this paper we show that it remains pspace-complete even if each round consists of only two questions.
rational subsets of partially reversible monoids. a class of monoids that can model partial reversibility allowing simultaneously instances of two-sided reversibility, one-sided reversibility and no reversibility is considered. some of the basic decidability problems involving their rational subsets, syntactic congruences and characterization of recognizability, are solved using purely automata-theoretic techniques, giving further insight into the structure of recognizable languages.
algorithms for subsequence combinatorics. a subsequence is obtained from a string by deleting any number of characters; thus in contrast to a substring, a subsequence is not necessarily a contiguous part of the string. counting subsequences under various constraints has become relevant to biological sequence analysis, to machine learning, to coding theory, to the analysis of categorical time series in the social sciences, and to the theory of word complexity. we present theorems that lead to efficient dynamic programming algorithms to count (1) distinct subsequences in a string, (2) distinct common subsequences of two strings, (3) matching joint embeddings in two strings, (4) distinct subsequences with a given minimum span, and (5) sequences generated by a string allowing characters to come in runs of a length that is bounded from above.
fast and compact regular expression matching. we study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word ram model of computation that allows logarithmic-sized words to be manipulated in constant time. we show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.
simulating one-reversal multicounter machines by partially blind multihead finite automata. this work is concerned with simulating nondeterministic one-reversal multicounter automata (ncms) by nondeterministic partially blind multihead finite automata (nfas). we show that any one-reversal ncm with k counters can be simulated by a partially blind nfa with k blind heads. this provides a nearly complete categorization of the computational power of partially blind automata, showing that the power of a (k+1)-nfa lies between that of a k-ncm and a (k+1)-ncm.
the pruning-grafting lattice of binary trees. we introduce a new lattice structure b"n on binary trees of size n. we exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. more precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in b"n equals to the eulerian numbers 2^n-(n+1) (resp. (n-1)^2) and that the number of coverings is (2nn-1). finally, we exhibit a matching in a constructive way. then we propose some open problems about this new structure.
rectangular polyomino set weak (1, 2)-achievement games. in a polyomino set (1, 2)-achievement game the maker and the breaker alternately mark one and two previously unmarked cells respectively. the maker's goal is to mark a set of cells congruent to one of a given set of polyominoes. the breaker tries to prevent the maker from achieving his goal. the teams of polyominoes for which the maker has a winning strategy is determined up to size 4. in set achievement games, it is natural to study infinitely large polyominoes. this enables the construction of super winners that characterize all winning teams up to a certain size.
dynamic bin packing of unit fractions items. this paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary times. we want to pack a sequence of unit fractions items (i.e., items with sizes 1/w for some integer w>=1) into unit-size bins, such that the maximum number of bins ever used over all time is minimized. tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. in particular, we show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2.45 and 2.4942. we also show that no on-line algorithm is better than 2.428-competitive.
a shared-variable concurrency analysis of multi-threaded object-oriented programs. in this paper a proof outline logic is introduced for the partial correctness of multi-threaded object-oriented programs like in java. the main contribution is a generalization of the owicki& gries proof method for shared-variable concurrency to dynamic thread creation. this paper also provides a formal justification of this generalization in terms of soundness and completeness proofs.
reactors: a data-oriented synchronous/asynchronous programming model for distributed applications. our aim is to define the kernel of a simple and uniform programming model-the reactor model-which can serve as a foundation for building and evolving internet-scale programs. such programs are characterized by collections of loosely-coupled distributed components that are assembled on the fly to produce a composite application. a reactor consists of two principal components: mutable state, in the form of a fixed collection of relations, and code, in the form of a fixed collection of rules in the style of datalog. a reactor's code is executed in response to an external stimulus, which takes the form of an attempted update to the reactor's state. as in classical process calculi, the reactor model accommodates collections of distributed, concurrently executing processes. however, unlike classical process calculi, our observable behaviors are sequences of states, rather than sequences of messages. similarly, the interface to a reactor is simply its state, rather than a collection of message channels, ports, or methods. one novel feature of our model is the ability to compose behaviors both synchronously and asynchronously. also, our use of datalog-style rules allows aspect-like composition of separately-specified functional concerns in a natural way.
scala actors: unifying thread-based and event-based programming. there is an impedance mismatch between message-passing concurrency and virtual machines, such as the jvm. vms usually map their threads to heavyweight os processes. without a lightweight process abstraction, users are often forced to write parts of concurrent applications in an event-driven style which obscures control flow, and increases the burden on the programmer. in this paper we show how thread-based and event-based programming can be unified under a single actor abstraction. using advanced abstraction mechanisms of the scala programming language, we implement our approach on unmodified jvms. our programming model integrates well with the threading model of the underlying vm.
pict correctness revisited. the pict programming language is an implementation of the @p-calculus in which executions of @p-calculus terms are specified via an abstract machine. an important property of any concurrent programming language implementation is the fair execution of threads. after defining fairness for the @p-calculus, we show that pict abstract machine executions implement fair @p-calculus executions. we also give new proofs of soundness and liveness for the pict abstract machine.
on the parameterized complexity of multiple-interval graph problems. multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. with this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. in this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. the problems under consideration are k-independent set, k-dominating set, and k-clique, which are all known to be w[1]-hard for general graphs, and np-complete for multiple-interval graphs. we prove that k-clique is in fpt, while k-independent set and k-dominating set are both w[1]-hard. we also prove that k-independent dominating set, a hybrid of the two above problems, is also w[1]-hard. our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing w[1]-hardness via a reduction from the k-multicolored clique problem, a variant of k-clique. we believe this technique has interest in its own right, as it should help in simplifying w[1]-hardness results which are notoriously hard to construct and technically tedious.
single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. we study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. this is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. we prove that threshold graphs and chain graphs admit such sequences. based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. minimum completions and deletions into these classes are np-hard to compute.
a cyclic binary morphism avoiding abelian fourth powers. we exhibit a cyclic binary morphism avoiding abelian fourth powers.
the hitting and cover times of random walks on finite graphs using local degree information. standard random walks on finite graphs select the vertex visited next to the adjacent vertices at random with the same probability. despite not using any global topological information, they guarantee o(n^3) hitting and cover times for any graph, where n is the order of the graph. motivated by network protocol applications, this paper investigates the impact of local topological information on designing ''better'' random walks. we first show that (a) for any transition probability matrix, the hitting (and hence the cover) time of a path graph is @w(n^2). we next investigate for any graph g=(v,e) a transition probability matrix p=(p(u,v))"u","v"@?"v defined by p(u,v)={deg^-^1^/^2(v)@?w@?n(u)deg^-^1^/^2(w)if v@?n(u),0otherwise ,where n(u) and deg(u) are respectively the set of adjacent vertices of u and the u's degree. random walks obeying this transition probability matrix are shown to guarantee the following: for any graph, (b) the hitting time is o(n^2), and (c) the cover time is o(n^2logn). facts (a) and (b) show that the degree information on the adjacent vertices is powerful enough for random walks to achieve the optimum hitting time.
finite n-tape automata over possibly infinite alphabets: extending a theorem of eilenberg et al. eilenberg, elgot and shepherdson showed in 1969, [s. eilenberg, c.c. elgot, j.c. shepherdson, sets recognized by n-tape automata, journal of algebra 13 (1969) 447-464], that a relation on finite words over a finite, non-unary alphabet with p letters is definable in first order logic with p+2 predicates for the relations equal length, prefix and last letter isa (for each letter a@?@s) if and only if it can be recognized by a finite multitape synchronous automaton, i.e., one whose read heads move simultaneously. they left open the characterization in the case of infinite alphabets, and proposed some conjectures concerning them. we solve all problems and sharpen the main theorem of [s. eilenberg, c.c. elgot, j.c. shepherdson, sets recognized by n-tape automata, journal of algebra 13 (1969) 447-464].
the minimal laplacian spectral radius of trees with a given diameter. for a graph g, its laplacian matrix is the difference of the diagonal matrix of its vertex degrees and its adjacency matrix. let t"n","d be the set of trees on n vertices with diameter d. in this paper, for d@?{1,2,3,4,n-3,n-2,n-1}, trees with minimal laplacian spectral radii in the set t"n","d are characterized.
amalgamating sessions and methods in object-oriented languages with generics. we suggest an amalgamation of communication-based programming (centered on sessions) and object-oriented programming, whereby sessions between concurrent threads are amalgamated with methods. in our proposal, threads consist of the execution of session bodies on objects and communicate with each other by asynchronously sending/receiving objects on channels. the response to a session request is based on the name of the request and the class of the object receiving the request. the decision of how to continue a session is based on the class of the object sent/received. sessions can be delegated to other sessions, although sessions themselves are not first class objects. we demonstrate our ideas through a core language with generic types, sam^g, and an example. we then formalize a small calculus, fsam^g, and prove subject reduction and progress. the latter property is notoriously difficult to achieve in concurrent calculi.
fault-tolerant computation of distributed regular path queries. regular path queries are the building blocks of almost any mechanism for querying semistructured data. despite the fact that the main applications of such data are distributed, there are only few works dealing with distributed evaluation of regular path queries. in this paper we present a message-efficient and truly distributed algorithm for computing the answer to regular path queries in a multi-source semistructured database setting. our algorithm is general as it works for the larger class of weighted regular path queries on weighted semistructured databases. also, we show how to make our algorithm fault-tolerant to smoothly work in environments prone to process (or machine) failures. this is very desirable in a grid setting, which is today's new paradigm of distributed computing, and where one does not have full control over machines that can unexpectedly leave in the middle of computation.
minimal interval completion through graph exploration. given an arbitrary graph g=(v,e) and an interval graph h=(v,f) with e@?f we say that h is an interval completion of g. the graph h is called a minimal interval completion of g if, for any sandwich graph h^'=(v,f^') with e@?f^'@?f, h^' is not an interval graph. in this paper we give a o(nm) time algorithm computing a minimal interval completion of an arbitrary graph. the output is an interval model of the completion.
fully abstract models and refinements as tools to compare agents in timed coordination languages. coordination languages and models promote the idea of separating computation and interaction aspects. as for traditional concurrency models, the question of safely replacing an agent by another one in any interacting context naturally appears. this paper proposes two tools to answer that question. on the one hand, a fully abstract semantics allows us to identify two processes which behave similarly in any context. on the other hand, a refinement theory allows us to compare processes that appear to be different in view of the fully abstract semantics but which satisfy the substitutability property: if the implementation i refines the specification s and if c[s] is deadlock free, for some context c, then c[i] is also deadlock free. both theories are novel, are exposed in the context of our timed coordination languages but may actually be transposed in the context of almost any data-driven coordination language.
complexity classes for self-assembling flexible tiles. we present a theoretical model for self-assembling dna tiles with flexible branches. we encode an instance of a ''problem'' as a pot of such tiles for which a ''solution'' is an assembled complete complex without any free sticky ends. using the number of tiles in an assembled complex as a measure of complexity we show how ntime classes (such as np and nexp) can be represented with corresponding classes of the model.