waashk/dblp huggingface dataset:
one query reducibilities between partial information classes. a partial information algorithm for a language a computes for m input words (x1,..., xm) a set of bitstrings containing χa(x1,..., xm). for a family d of sets of bitstrings of length m, a ∈ p[d] if there is a polynomial time partial information algorithm that always outputs a set from d. for the case m = 2 we investigate whether for families d1 and d2 the languages in p[d1] are reducible to languages in px[d2] for some x in the polynomial hierarchy ph or in exp. several nonreducibilities follow from known structural properties of classes p[d]. beigel et al. [membership comparable and p-selective sets, technical report 2002-006n, nec research institute, 2002] showed nonreducibility from strongly 2-membership comparable languages to p-selective languages. they also showed one query (1-tt, for short) reducibility from 2-cheatable languages to p-selective languages. a proof of tantau [combinatorial representations of partial information classes and their truth-table closures, master's thesis, tu berlin, germany, 1999] yields a 1-tt reducibility from 2-cheatable languages to languages in pς2p[min2]. we achieve results for all remaining non-trivial pairs of classes p[d] for m = 2. our positive results all show 1-tt reducibilities. our negative results even hold if the reducing machines as well as the partial information algorithms for the languages we try to reduce to have access to oracles in exp. we show: 1. the 2-cheatable languages are 1-tt δ2p-reducible to languages in δ2p[min2]. 2. languages in p[sel2 ∪ {xor2}] are 1-tt δ2p-reducible to δ2p-selective languages. 3. the easily 2-countable languages are 1-tt δ3p-reducible to δ3p-strongly-2-membership-comparable languages. 4. the 2-membership comparable languages are 1-tt e-reducible to e-strongly-2-membership-comparable languages. 5. there are easily 2-countable languages which are not turing exp-reducible to languages in exp[bottom2]. 6. there are languages in p[bottom2] which are not 1-tt exp-reducible to exp-selective languages.
compositional analysis of contract-signing protocols. we develop a general method for proving properties of contract-signing protocols using a specialized protocol logic. the method is applied to the asokan-shoup--waidner and the garay-jacobson-mackenzie protocols. our method offers certain advantages over previous analysis techniques. first, it is compositional: the security guarantees are proved by combining the independent proofs for the three subprotocols of each protocol. second, the formal proofs are carried out in a "template" form, which gives us a reusable proof that may he instantiated for the two example protocols, as well as for other protocols with the same arrangement of messages. third, the proofs follow the design intuition. in particular, in proving game-theoretic properties like fairness, we demonstrate success for the specific strategy that the protocol designer had in mind, instead of non-constructively proving that a strategy exists. finally, our logical proofs demonstrate security when an unbounded number of sessions are executed in parallel.
a brief history of process algebra. this note addresses the history of process algebra as an area of research in concurrency theory, the theory of parallel and distributed systems in computer science. origins are traced back to the early seventies of the twentieth century, and developments since that time are sketched. the author gives his personal views on these matters. he also considers the present situation, and states some challenges for the future.
fringe analysis of synchronized parallel insertion algorithms in 2-3 trees. fringe analysis uses the distribution of bottom subtrees or fringe of search trees under the assumption of random insertion of keys, yielding an average case analysis of the fringe. the results in the fringe give upper and lower bounds for several measures for the whole tree.we are interested in the fringe analysis of the synchronized parallel insertion algorithms of paul, vishkin, and wagener (pvw) on 2-3 trees. this algorithm inserts k keys with k processors into a tree of size n with time o(log n + log k). as the direct analysis of this algorithm is very difficult we tackle this problem by introducing a new family of algorithms, denoted by macrosplit algorithms, and our main theorem proves that two algorithms of this family, denoted maxmacrosplit and minmacrosplit, bound the behavior of the fringe in the pvw algorithm.previous work deals with the fringe analysis of sequential algorithms, but this type of analysis was still an open problem for parallel algorithms on search trees. we extend fringe analysis to parallel algorithms and we get a rich mathematical structure giving new interpretations even in the sequential case. we prove that random insertion of keys generates a binomial distribution, that the synchronized insertion of keys can be modeled by a markov chain, and that the coefficients of the transition matrix of the markov chain are related to the expected local behavior of our algorithm. finally, we show that the coefficients of the power expansion of this matrix over (n + 1)-1 are the binomial transform of the expected local behavior of the algorithm. we finally show that the fringe of the pvw algorithm asymptotically converges to the sequential case.
polynomial and apx-hard cases of the individual haplotyping problem. snp haplotyping problems have been the subject of extensive research in the last few years, and are one of the hottest areas of computational biology today. in this paper we report on our work of the last two years, whose preliminary results were presented at the european symposium on algorithms (proceedings of the annual european symposium on algorithms (esa), vol. 2161. lecture notes in computer science, springer, 2001, pp. 182-193.) and workshop on algorithms in bioinformatics (proceedings of the annual workshop on algorithms in bioinformatics (wabi), vol. 2452. lecture notes in computer science, springer, 2002, pp. 29-43.). we address the problem of reconstructing two haplotypes for an individual from fragment assembly data. this problem will be called the single individual haplotyping problem. on the positive side, we prove that the problem can be solved effectively for gapless data, and give practical, dynamic programming algorithms for its solution. on the negative side, we show that it is unlikely that polynomial algorithms exist, even to approximate the solution arbitrarily well, when the data contain gaps. we remark that both the gapless and gapped data arise in different real-life applications.
short length menger's theorem and reliable optical routing. in the minimun path coloring problem, we are given a graph and a set of pairs of vertices of the graph and we are asked to connect the pairs by colored paths in such a way that paths of the same color are edge disjoint. in this paper we deal with a generalization of this problem where we are asked to connect each pail by k edge disjoint paths of the same color. the objective is to minimize the number of colors. the reason for multiple paths between the same pair of vertices is to ensure fault tolerance of the connections. we propose an o(k2f) = o(k2δα-1 log n) approximation algorithm for this problem where f is the flow number of the graph, δ is the maximum degree and α is the expansion. this is an improvement even for the special case k = 1 where, to our knowledge, the best previously known bound is weaker by a factor of log n.the underlying problem is that of finding several disjoint paths between a given pair of vertices. menger's theorem provides a necessary and sufficient condition for the existence of k such paths. however, it does not say anything about the length of the paths although in communication problems the number of links used is an issue. we show that any two k-connected vertices are connected by k edge disjoint paths of average length o(kf) which improves an earlier result of galil and yu (proceedings of the 27th annual acm symposium on theory of computing, 1995) for several classes of graphs. in fact, this is only a corollary of a stronger result for multicommodity flow on networks with unit edge capacities: any multicommodity flow with k units for each commodity can be rerouted such that the flow for each commodity is shipped through k-tuples of edge disjoint paths of average length o(kf) without exceeding the edge capacities significantly.
set-sharing is redundant for pair-sharing. although the usual goal of sharing analysis is to detect which pairs of variables share, the standard choice for sharing analysis is a domain that characterizes set-sharing. in this paper, we question, apparently for the first time, whether this domain is over-complex for pair-sharing analysis. we show that the answer is yes. by defining an equivalence relation over the set-sharing domain we obtain a simpler domain, reducing the complexity of the abstract unification procedure. we present experimental results showing that, in practice, our domain compares favorably with the set-sharing one over a wide range of benchmark and real programs. copyright 2002 elsevier science b.v.
inverse eigenproblem for centrosymmetric and centroskew matrices and their approximation. in this paper, we first give the solvability condition for the following inverse eigenproblem (iep): given a set of vectors {xi}i=1m in cn and a set of complex numbers {λi}i=1m, find a centrosymmetric or centroskew matrix c in rn × n such that {xi}i-1m and {λi}i-1m are the eigenvectors and eigenvalues of c, respectively. we then consider the best approximation problem for the ieps that are solvable. more precisely, given an arbitrary matrix b in rn × n, we find the matrix c which is the solution to the iep and is closest to b in the frobenius norm. we show that the best approximation is unique and derive an expression for it.
efficient computation of time-bounded reachability probabilities in uniform continuous-time markov decision processes. a continuous-time markov decision process (ctmdp) is a generalization of a continuous-time markov chain in which both probabilistic and nondeterministic choices co-exist. this paper presents an efficient algorithm to compute the maximum (or minimum) probability to reach a set of goal states within a given time bound in a uniform ctmdp, i.e., a ctmdp in which the delay time distribution per state visit is the same for all states. it furthermore proves that these probabilities coincide for (time-abstract) history-dependent and markovian schedulers that resolve nondeterminism either deterministically or in a randomized way.
on the decidability of the termination problem of active database systems. active database systems enhance the functionality of traditional databases through the use of active rules or 'triggers'. one of the principal analysis questions for such systems is that of termination--is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. in this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. we present results for two broad types of variations, variations in rule syntax and variations in meta level features. within each of these, we identify members close to the boundary of (un)decidability and also look at the effect of combining members of each type. the maximal decidable class we present is capable of expressing some useful kinds of application requirements, such as checking and repairing inclusion constraints. the work is also interesting from a theoretical point of view, since the context is similar to the while query language and the dynamics gives an interesting contrast to datalog with negation.
stratified coherence spaces: a denotational semantics for light linear logic. light linear logic (lll) was introduced by girard as a logical system capturing the class of polytime functions within the proofs-as-programs approach. in the present paper, we undertake a semantical analysis of lll: a variant of coherence spaces is introduced and we prove that it is a sound model for this system, but not for usual linear logic. a simpler version of the model yields a sound semantics of elementary linear logic, which is the analog of lll for the class of kalmar elementary functions. we illustrate our semantical method by showing how various principles fail in these models.
component composition preserving behavioral contracts based on communication traces. this paper investigates the compositional properties of reusable software components defined with explicit dependencies and behavioural contracts expressing rely-guarantee specifications in the form of communication traces. in this setting, connection of components through their matching ports is indeed compositional and yields a new component or composite that respects its constituents' contracts. thus the behaviour of the composite is computed from the behaviours of its constituents and is known to conform to the contracts without any new proof.
normalization, approximation, and semantics for combinator systems. this paper studies normalization of typeable terms and the relation between approximation semantics and filter models for combinator systems. it presents notions of approximants for terms, intersection type assignment, and reduction on type derivations; the last will be proved to be strongly normalizable. with this result, it is proved that every typeable term has an approximant with the same type, and a characterization of the normalization behaviour of terms using their assignable types is given. then the two semantics are defined and compared, and it is shown that the approximants semantics is fully abstract but the filter semantics is not.
the consistency dimension and distribution-dependent learning from queries. we prove a new combinatorial characterization of polynomial learnability from equivalence queries, and state some of its consequences relating the learnability of a class with the learnability via equivalence and membership queries of its subclasses obtained by restricting the instance space. then we propose and study two models of query learning in which there is a probability distribution on the instance space, both as an application of the tools developed from the combinatorial characterization and as models of independent interest.
domain and event structure semantics for petri nets with read and inhibitor arcs. we propose a functorial concurrent semantics for petri nets extended with read and inhibitor arcs, that we call inhibitor nets. along the lines of the seminal work by winskel on safe (ordinary) nets, the truly concurrent semantics is given at a categorical level via a chain of coreflections leading from the category sw-in of semi-weighted inhibitor nets to the category dom of finitary prime algebraic domains (equivalent to the category pes of prime event structures). as an intermediate semantic model, we introduce inhibitor event structures, an event-based model able to faithfully capture the dependencies among events which arise in the presence of read and inhibitor arcs. inhibitor event structures generalise several event structure models in the literature, like prime, asymmetric and bundle event structures.
an improvement of the construction of the d.v. and g.v. chudnovsky algorithm for multiplication in finite fields. from an interpolation method on algebraic curves, due to d.v. chudnovsky and g.v. chudnovsky, we give a new method for the construction of bilinear algorithms for multiplication in the extensions of finite fields. we obtain algorithms better than known ones.
private computation using a pez dispenser. we show how a (big) pez dispenser can be used by two or more players to compute a function of their inputs while hiding the values of the inputs from each other. in contrast to traditional approaches for solving this problem, ours does not require any use of randomness.
on the edge-bandwidth of graph products. the edge-bandwidth of a graph g is the bandwidth of the line graph of g. we show asymptotically tight bounds on the edge-bandwidth of two-dimensional grids and tori, the product of two cliques and the n-dimensional hypercube.
an approximation algorithm for the precedence constrained scheduling problem with hierarchical communications. we study the problem of minimizing the makespan for the precedence multiprocessor constrained scheduling problem with hierarchical communications (parallel process. lett. 10(1) (2000) 133). we propose an 8/5-approximation algorithm for the unit communication time hierarchical problem with arbitrary but integer processing times and an unbounded number of biprocessor machines. we extend this result in the case where each cluster has m processors (where m is a fixed constant) by presenting a (2 - 2/(2m + 1))-approximation algorithm.
basic analytic combinatorics of directed lattice paths. this paper develops a unified enumerative and asymptotic theory of directed two-dimensional lattice paths in half-planes and quarter-planes. the lattice paths are specified by a finite set of rules that are both time and space homogeneous, and have a privileged direction of increase. (they are then essentially one-dimensional objects.) the theory relies on a specific "kernel method" that provides an important decomposition of the algebraic generating functions involved, as well as on a generic study of singularities of an associated algebraic curve. consequences are precise computable estimates for the number of lattice paths of a given length under various constraints (bridges, excursions, meanders) as well as a characterization of the limit laws associated to several basic parameters of paths.
a geometric interpretation of ld-resolution. we devise an interpretation of a binarised definite logic program in a geometric framework which is closer to dynamical systems than to logic. the building blocks of our framework are a family of affine sub-modules in a free finitely generated module over a special kind of ring. we describe sld-resolution of definite binary programs as the iterated action of a finite union of affine graphs, associated to the program clauses, on a certain set of affine varieties associated to the original syntactic terms. this action is shown to faithfully represent the running of the corresponding program on a given goal, since all answers and only those answers the program would output are obtained. hence, a programming language such as pure prolog completely falls within our description.
rearrangeability of bit permutation networks. in this paper, we introduce the concept of routing grid as a tool for analyzing realizability of permutations on bit permutation networks (bpns). we extend a result by linial and tarsi which characterizes permutations realizable on shuffle-exchange networks to any bpns. a necessary condition for a bpn to he rearrangeable is given, and the rearrangeability of two families of bpns are explored. finally, we present a method which may help to tackle one kind of balanced matrix problems whose solution implies an answer to benes conjecture. hopefully, our treatment brings some new insight into the problem of permutation routing.
on unique graph 3-colorability and parsimonious reductions in the plane. we prove that the satisfiability (resp. planar satisfiability) problem is parsimoniously p-time reducible to the 3-colorability (resp. planar 3-colorability) problem, that means that the exact number of solutions is preserved by the reduction, provided that 3-colorings are counted modulo their six trivial color permutations. in particular, the uniqueness of solutions is preserved, which implies that unique 3-colorability is exactly as hard as unique satisfiability in the general case as well as in the planar case. a consequence of our result is the dp-completeness of unique 3-colorability and unique planar 3-colorability under random p-time reductions. it also gives a finer and unified proof of the #p-completeness of #3-colorability that was first obtained by linial for the general case, and later by hunt et al. for the planar case. previous authors' reductions were either weakly parsimonious with a multiplication of the numbers of solutions by an exponential factor, or involved #p-complete intermediate counting problems derived from trivial "yes"-decision problems.
a full continuous model of polymorphism. we introduce a model of the second-order lambda calculus. such a model is a scott domain whose elements are themselves scott domains, and in it polymorphic maps are interpreted by generic continous maps.
symmetries of decimation invariant sequences and digit sets. a bi-infinite sequence is called p-decimation invariant if all p-decimations of it reproduce the sequence albeit with a shift. in this paper we discuss symmetry properties of decimation invariant sequences. a symmetry is a composition of a translation and a reflection. we establish the existence of translation invariant, i.e., periodic, decimation invariant sequences. moreover, we prove that there exist decimation invariant sequences which are left-periodic and right-periodic, i.e., they are partially translation invariant. we present several criteria for the existence of decimation invariant sequences with additional periodicity properties. finally, we discuss the existence of decimation invariant sequences that are invariant under reflections. moreover, in passing we demonstrate that properties of decimation invariant sequences are linked with properties of certain digit sets.
the pascal matroid as a home for generating sets of cellular automata configurations defined by quasigroups. consider a one-dimensional ca whose local evolution rule is defined by a quasigroup (g,*). when the initial state is only known over a finite string of adjacent cells, the ca's orbit (state-time diagram) is only defined on a triangular array of cells. this well-defined triangular part of the orbit, in which each cell has a value in g, is called a (g,*)-configuration. a generating set is a subset of the triangular array such that any attribution of g-values to the cells of this subset determines a unique (g,*)-configuration. it turns out that the collection of all potential generating sets form a particular matroid, which we have called the pascal matroid. the main subject of this work is related to the question whether every base of this matroid actually occurs as a generating set for a (g,*)-configuration.
averages of automatic sequences. we give some sufficient criteria for the existence of certain averages (mean, correlation functions) of generalized higher-dimensional automatic sequences and show how to calculate these averages. then follows an exploration of the nature of necessary and sufficient conditions for the existence of averages. some of these criteria are applied to averages which play a central role in the determination of the correlation function of an automatic sequence.
transposing partial components - an exercise on coalgebraic refinement. a partial component is a process which fails or dies at some stage, thus exhibiting a finite, more ephemeral behaviour man expected. partiality--which is the rule rather than exception in formal modelling--can be treated mathematically via totalization techniques. in the case of partial functions, totalization involves error values and exceptions.in the context of a coalgebraic approach to component semantics, this paper argues that the behavioural counterpart to such functional techniques should extend behaviour with try-again cycles preventing from component collapse, thus extending totalization or transposition from the algebraic to the coalgebraic context.we show that a refinement relationship holds between original and totalized components which is reasoned about in a coalgebraic approach to component refinement expressed in the pointfree binary relation calculus.as part of the pragmatic aims of this research, we also address the factorization of every such totalized coalgebra into two coalgebraic components--the original one and an added front-end--which cooperate in a client-server style.