waashk/dblp huggingface dataset:
sequential and parallel algorithms for the nca problem on pure pointer machines. we present a simple, arithmetic-free, efficient scheme to compress trees maintaining the nca information. we use this compression scheme to provide an o(n + q lg lg n) solution for solving the nca problem on pure pointer machines (ppms)--i.e., pointer machines with no arithmetic capabilities--in both the static and dynamic case, where n is the number of add-leaf/delete operations and q is the number of nca queries. this solution is optimal. we also extend the solution to a parallel pointer machine algorithm. the algorithm assumes that the tree t is known in advance and it requires o(lg n) parallel time and o(n) processors for pre-processing where n is the number of nodes in the tree. thereafter, it can answer any nca query in o(lg lg n) time using a single processor. to our knowledge, this is the best known parallel pointer machine algorithm for the nca problem. our nca algorithm requires an efficient parallel solution of the temporal precedence problem [ranjan et al., the temporal precedence problem, algorithmica 28 (2000) 288-306]. we provide an efficient parallel pointer machine algorithm to solve this problem as well.
iterative inversion of structured matrices. iterative processes for the inversion of structured matrices can be further improved by using a technique for compression and refinement via the least-squares computation. we review such processes and elaborate upon incorporation of this technique into the known frameworks.
quantifiers and approximation. we investigate the relationship between logical expressibility of np optimization problems and their approximation properties. first such attempt was made by papadimitriou and yannakakis, who defined the class of npo problems max np. we show that many important optimization problems do not belong to max np and that in fact there are problems in p which are not is maxnp. the problems we consider fit naturally in a new complexity class that we call max ii sub 1. we prove that several natural optimization problems are complete for max ii sub 1 under approximation preserving reductions. all these complete problems are non-approximable unless p=np. this motivates the definition of subclasses of max ii sub 1 that only contain problems which are presumably easier with respect to approximation. in particular, the class that we call rmax(2), contains approximable problems and problems like max clique that are not known to be non-approximable. we prove that max clique and other natural optimization problems are complete for rmax(2). all the complete problems in rmax(2) share the interesting property that they either are non-approximable or are approximable to any degree of accuracy.
analysis of multiple quickselect variants. multiple quickselect is an algorithm that uses the idea of quicksort to search for several order statistics simultaneously. in order to improve the efficiency of quicksort, one can use the median of 2t + 1 randomly chosen elements as pivot element in the partitioning stage. such a median of 2t + 1 partition can also be applied to multiple quickselect to reduce the number of comparisons. here we give an analysis of such multiple quickselect variants that use median of 2t + 1 partition and describe for these algorithms the asymptotic behaviour of the expected number of required comparisons to find p-order statistics in a data set of size n for n → ∞ and fixed p.
on a conjecture related to geometric routing. we conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the euclidean distance to t decreases monotonically along the path. a consequence of this conjecture would be that in any ad hoc network containing such a graph as a spanning subgraph, two-dimensional virtual coordinates for the nodes can be found for which the method of purely greedy geographic routing is guaranteed to work. we discuss this conjecture and its equivalent forms show that its hypothesis is as weak as possible, and show a result delimiting the applicability of our approach: any 3-connected k3,3-free graph has a planar 3-connected spanning subgraph. we also present two alternative versions of greedy routing on virtual coordinates that provably work. using steinitz's theorem we show that any 3-connected planar graph can be embedded in three dimensions so that greedy routing works, albeit with a modified notion of distance; we present experimental evidence that this scheme can be implemented effectively in practice. we also present a simple but provably robust version of greedy routing that works for any graph with a 3-connected planar spanning subgraph.
hierarchies for classes of priority algorithms for job scheduling. priority algorithm is a model of computation capturing the notion of greedy and greedy-like algorithm. this paper concerns priority algorithms for job scheduling. three main restrictions are defined for priority algorithms, namely: memoryless, greedy and fixed. it was asked in [a. borodin, m.n. nielsen, c. rackoff, (incremental) priority algorithms, in: proc. 13th annu. symp. discrete algorithms (soda), january 2002, pp. 752-761 (also in algorithmica 37(4) (2003) 295-326] whether the general class of priority algorithms is of different power from the restricted class of greedy-priority algorithms (for the job scheduling problem). we answer this question affirmatively by showing that a specific priority algorithm cannot be simulated by any greedy-priority algorithm on every input. furthermore we systematically compare every two classes of priority algorithms for different settings of job scheduling. we also define a hierarchy for priority algorithms of bounded memory which lies between the class of memoryless and the class of priority algorithms with memory, and we show that this memory hierarchy is robust.
deformation techniques to solve generalised pham systems. in heintz et al. (electron. j. sadio 1(1) (1998) 37), castro et al. (found., comput. math. (2003) to appear) and pardo (proceedings eaca'2000, 2000, pp. 25-51), the authors have shown that universal solving procedures require exponential running time. roughly speaking, a universal solving procedure takes as input a system of multivariate polynomial equations and outputs complete symbolic information on the solution variety. here, we introduce a nonuniversal solving procedure adapted to generalised pham systems. the aim is to compute partial information of the variety defined by the input system. the algorithm is based on an homotopic deformation and on a non-archimedean lifting procedure from a non-singular zero of the homotopy curve. the complexity of the procedure is also stated and it depends on some intrinsic quantity called the deformation degree of the given input system.
three concepts of decidability for general subsets of uncountable spaces. there is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. here we consider three notions: decidability up to measure zero [m.w. parker, undecidability in rn: riddled basins, the kam tori, and the stability of the solar system, phil. sci. 70(2) (2003) 359-382], which we abbreviate d.m.z.; recursive approximability [or r.a.; k.-i. ko, complexity theory of real functions, birkhäuser, boston, 1991]; and decidability ignoring boundaries [d.i.b.; w.c. myrvold, the decision problem for entanglement, in: r.s. cohen et al. (eds.), potentiality, entanglement, and passion-at-a-distance: quantum mechanical studies fo abner shimony, vol. 2, kluwer academic publishers, great britain, 1997, pp. 177-190]. unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in rn and other appropriate spaces. we consider some motivations for these concepts and the logical relations between them. it has been argued that d.m.z. is especially appropriate for physical applications, and on rn with the standard measure, it is strictly stronger than r.a. [m.w. parker, undecidability in rn: riddled basins, the kam toil, and the stability of the solar system, phil. sci. 70(2) (2003) 359-382]. here we show that this is the only implication that holds among our three decidabilities in that setting. under arbitrary measures, even this implication fails. yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent.
on computing hilbert bases via the elliot-macmahon algorithm. the ways of using the elliot-macmahon algorithm to compute the hilbert base of a system of linear diophantine equations known so far are either not efficient or can fail to terminate. we present a version of an algorithm exploiting this range of ideas, which however is reasonably efficient as well as finite.
coalgebraic modal logic: soundness, completeness and decidability of local consequence. this paper studies finitary modal logics, interpreted over coalgebras for an endofunctor, and establishes soundness, completeness and decidability results. the logics are studied within the abstract framework of coalgebraic modal logic, which can be instantiated with arbitrary endofunctors on the category of sets. this is achieved through the use of predicate liftings, which generalise atomic propositions and modal operators from kripke models to arbitrary coalgebras. predicate liftings also allow us to use induction along the terminal sequence of the underlying endofunctor as a proof principle. this induction principle is systematically exploited to establish soundness, completeness and decidability of the logics. we believe that this induction principle also opens new ways for reasoning about modal logics: our proof of completeness does not rely on a canonical model construction, and the proof of the finite model property does not use filtrations.
a coordination approach to mobile components. we present a calculus for mobile systems, the main novel feature of which is the separation between dynamic and topological aspects of distributed computations. our calculus realises the following basic assumptions: (1) every computation executes in a uniquely determined location, (2) processes modify the distributed structure by means of predefined operations, (3) the underlying programming language can be changed easily, and (4) locations are hierarchically organised. this paper introduces our calculus, and shows, that this separation of concerns leads to a perfect match between the logical, syntactical and algebraic theory. we discuss a core calculus, and extensions with local names and with multiple names.
realizing boolean functions on disjoint sets of variables. for switching functions $f$ let $c(f)$ be the combinatorial complexity of $f$. we prove that for every $\varepsilon < 0$ there are arbitrarily complex functions $f:\{0,1\}^{n} \rightarrow \{0,1\}^{n}$ such that $c(fxf) \leq (1+ \varepsilon) c(f)$ and arbitrarily complex functions $g:\{0,1\}$ such that $c(v c(fxf)) \leq (1 + \varepsilon)c(f)$. these results and the techniques developed to obtain them are used to show, that ashenhurst decomposition of switching functions does not always yield optimal circuits and to prove a new result concerning the trade-off between circuit size and monotone circuit size. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
a guide to membrane computing. membrane systems are models of computation which are inspired by some basic features of biological membranes. in a membrane system multisets of objects are placed in the compartments defined by the membrane structure, and the objects evolve by means of "reaction rules" also associated with the compartments, and applied in a maximally parallel, nondeterministic manner. the objects can pass through membranes, the membranes can change their permeability, they can dissolve, and they can divide. these features are used in defining transitions between configurations of the system, and sequences of transitions are used to define computations. in the case of symbol-objects, we compute a set of numbers, and in the case of string-objects we compute a set of strings, hence a language. many different classes of such computing devices (now called p systems) have already been investigated. most of them are computationally universal, i.e., equal in power to turing machines. systems with an enhanced parallelism are able to trade space for time and solve in this way (at least in principle), by making use of an exponential space, intractable problems in a feasible time.the present paper presents the basic ideas of computing with membranes and some fundamental properties (mostly concerning the computational power and efficiency) of p systems of various types.
the continuum as a final coalgebra. we define the continuum up to order isomorphism, and hence up to homeomorphism via the order topology, in terms of the final coalgebra of either the functor nx, product with the set of natural numbers, or the functor 1+nx. this makes an attractive analogy with the definition of n itself as the initial algebra of the functor 1+x, disjoint union with a singleton. we similarly specify baire space and cantor space in terms of these final coalgebras. we identify two variants of this approach, a coinductive definition based on final coalgebraic structure in the category of sets, and a direct definition as a final coalgebra in the category of posets. we conclude with some paradoxical discrepancies between continuity and constructiveness in this setting.
greedy expansions and sets with deleted digits. we generalize a result of daróczy and kátai, on the characterization of univoque numbers with respect to a non-integer base (publ. math. debrecen 46(3-4) (1995) 385) by relaxing the digit alphabet to a generic set of real numbers. we apply the result to derive the construction of a büchi automaton accepting all and only the greedy sequences for a given base and digit set. in the appendix, we prove a more general version of the fact that the expansion of an element x ∈ q(q) is ultimately periodic, if q is a pisot number.
optimistic atomic broadcast: a pragmatic viewpoint. this paper presents the optimistic atomic broadcast algorithm (opt-abcast) which exploits the spontaneous total-order property experienced in local-area networks in order to allow fast delivery of messages. the opt-abcast algorithm is based on a sequence of stages, and messages can be delivered during a stage or at the end of a stage. during a stage, processes deliver messages fast. whenever the spontaneous total-order property does not hold, processes terminate the current stage and start a new one by solving a consensus problem which may lead to the delivery of some messages. we evaluate the efficiency of the opt-abcast algorithm using the notion of delivery latency.
playing by searching: two strategies against a linearly bounded liar. the problem of searching in the presence of errors is modeled as a game between a questioner and a responder. the responder chooses an integer x ∈ {1,..., n}, and the questioner has to determine x by asking a predetermined number of queries. the responder can lie at his pleasure, provided that at the end of the game the fraction of lies does not exceed a certain constant r. it is known that the questioner may win the game if and only if r < 1/3;. under the latter hypothesis, we state a lower bound on the number q(n, r) of queries needed by the questioner to win the game, even if he is allowed for arbitrary membership queries. next, we analyze two questioning strategies for the model where only comparison queries are allowed. the first strategy improves on the known upper bound on q(n,r); the second one achieves the same value of q(n,r), but makes also sure that each query can be formulated in constant time.
searching games with errors - fifty years of coping with liars. this is a survey on searching with errors, considered in the framework of two-person games. the responder thinks of an object in the search space, and the questioner has to find it by asking questions to which the responder provides answers, some of which are erroneous. we give a taxonomy of such games, depending on the type of questions allowed, on the degree of interactivity between the players, and on the imposed limitations on errors. we survey the existing results concerning such games, concentrating on the issue of optimizing the questioner's querying strategy, and pointing out open problems. we show the relations between searching games with errors and problems concerning communication through a noisy channel and error-correcting codes. finally, we discuss other search and computation problems with faulty feedback which are related to searching with errors
a compositional framework for fault tolerance by specification transformation. the incorporation of a recovery algorithm into a program can be viewed as a program transformation, converting the basic program into a fault-tolerant version. we present a framework in which such program transformations are accompanied by a corresponding formula transformation which obtains properties of the fault-tolerant versions of the programs from properties of the basic programs. compositionality is achieved when every property of the fault-tolerant version can be obtained from a transformed property of the basic program. a verification method for proving the correctness of formula transformations is presented. this makes it possible to prove just once that a formula transformation corresponds to a program transformation, removing the need to prove separately the correctness of each transformed program. keywords: parallel algorithms, distributed algorithms, fault-tolerance, specification, verification.
local majorities, coalitions and monopolies in graphs: a review. this paper provides an overview of recent developments concerning the process of local majority voting in graphs, and its basic properties, from graph theoretic and algorithmic standpoints.
informative labeling schemes for graphs. this paper introduces the notion of informative labeling schemes for arbitrary graphs. let f(w) be a function on subsets of vertices w. an f labeling scheme labels the vertices of a weighted graph g in such a way that f(w) can be inferred (or at least approximated) efficiently for any vertex subset w of g by merely inspecting the labels of the vertices of w, without having to use any additional information sources.a number of results illustrating this notion are presented in the paper. we begin by developing f labeling schemes for three functions f over the class of n-vertex trees. the first function, seplevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. the second, lca, provides the least common ancestor of any two vertices. the third, center, yields the center of any three given vertices v1, v2, v3 in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. all of these three labeling schemes use o(log2 n)-bit labels, which is shown to be asymptotically optimal.our main results concern the function steiner(w), defined for weighted graphs. for any vertex subset w in the weighted graph g, steiner(w) represents the weight of the steiner tree spanning the vertices of w in g. considering the class of n-vertex trees with m-bit edge weights, it is shown that for this class there exists a steiner labeling scheme using o((m + log n)log n) bit labels, which is asymptotically optimal. it is then shown that for the class of arbitrary n-vertex graphs with m-bit edge weights, there exists an approximate-steiner labeling scheme, providing an estimate (up to a factor of o(log n)) for the steiner weight steiner(w) of a given set of vertices w, using o((m + log n)log2 n) bit labels.
the first order theory of primal grammars is decidable. the formalism of primal grammars is one of the most powerful term schematization languages (theoret. comput. sci. 176(1-2) (1997) 111). in this paper, we describe an algorithm to check the satisfiability of first-order formulae in the theory of primal grammars. the correctness, completeness and termination of the algorithm are proven. the core of the procedure is the universal quantifier elimination method, which is based on a new explosion rule especially devoted to handle primal terms.
efficient transitive closure of sparse matrices over closed semirings. this paper surveys several alternative data structures and algorithms for multiplying sparse upper-triangular matrices over closed semirings, and evaluates their efficiency in computing transitive closures of matrices over the boolean semiring. two new variants are introduced that outperform previously known methods on a collection of large data-sets drawn from linguistic applications.
lambek calculus is np-complete. we prove that for both the lambek calculus l and the lambek calculus allowing empty premises l* the derivability problem is np-complete. it follows that also for the multiplicative fragments of cyclic linear logic and noncommutative linear logic the derivability problem is np-complete.
parametrization of approximate algebraic curves by lines. it is well known that irreducible algebraic plane curves having a singularity of maximum multiplicity are rational and can be parametrized by lines. in this paper, given a tolerance ε > 0 and an ε-irreducible algebraic plane curve l of degree d having an ε-singularity of multiplicity d - 1, we provide an algorithm that computes a proper parametrization of a rational curve that is exactly parametrizable by lines. furthermore, the error analysis shows that under certain initial conditions that ensures that points are projectively well defined, the output curve lies within the offset region of l at distance at most 2√2ε1(2d)exp(2).
approximating algebraic functions by means of rational ones. in this paper, we use eco method and the concept of succession rule to enumerate restricted classes of combinatorial objects. let &&ohgr; be the succession rule describing a construction of a combinatorial objects class, then the construction of the restricted class is described by means of an approximating succession rule &ohgr;rk obtained from &&ohgr; in a natural way. we give sufficient conditions for the rule k to be finite; finally we determine finite approximating rules for various classes of paths, and the approximation of the corresponding algebraic language with a regular one.
the asymptotic distribution of elements in automatic sequences. in an automatic sequence an element need not have an asymptotic density. in this paper a necessary and sufficient criterion is proved for the existence of the asymptotic density of a given element. if it does not exist the asymptotic distribution of the element can be described in terms of a function h whose graph is self-similar. an algorithm is given to decide whether h is piecewise continuously differentiable, and in this case it can be computed effectively. finally, it is shown that the h∞-density of an element in an automatic sequence always exists and equals its logarithmic density.
unary algebras, semigroups and congruences on free semigroups. in the triangle consisting of automata, languages and semigroups various correspondences of eilenberg's type between languages and semigroups and between automata and languages are known, and it remains to establish similar connections between automata and semigroups. in this paper we consider a more general case by taking unary x-algebras instead of automata and we establish complete lattice isomorphisms between the lattices of σ-varieties of x-algebras, κ-varieties of semigroups and weakly invariant congruences on the free semigroup x+, where κ is the cardinality of x, between the lattices of generalized σ-varieties of x-algebras, generalized κ-varieties of semigroups and filters of the lattice of weakly invariant congruences on x+, and between the lattices of pseudo-σ-varieties of x-algebras and pseudo-κ-varieties of semigroups.