waashk/dblp huggingface dataset:
two tapes are better than one for off-line turing machines we prove the first superlinear lower bound for a concrete decision problem in p on a turing machine with one work tape and a two-way input tape (also called: off-line 1-tape turing machine). in particular we show for off-line turing machines that 2 tapes are better than 1 and that 3 pushdown stores are better than 2 (both in the deterministic and in the nondeterministic case).
on contention resolution protocols and associated probabilistic phenomena. consider an on-line scheduling problem in which a set of abstract processes are competing for the use of a number of resources. further assume that it is either prohibitively expensive or impossible for any two of the processes to directly communicate with one another. if several processes simultaneously attempt to allocate a particular resource (as may be expected to occur, since the processes cannot easily coordinate their allocations), then none succeed. in such a framework, it is a challenge to design efficient contention resolution protocols.two recently-proposed approaches to the problem of pram emulation give rise to scheduling problems of the above kind. in one approach, the resources (in this case, the shared memory cells) are duplicated and distributed randomly. we analyze a simple and efficient deterministic algorithm for accessing some subset of the duplicated resources. in the other approach, we analyze how quickly we can access the given (nonduplicated) resource using a simple randomized strategy. we obtain precise bounds on the performance of both strategies. we anticipate that our results with find other applications.
classification of computable functions by primitive recursive classes a classification of all the computable functions is given in terms of subrecursive programming languages. these classes are those which also arise from the relation &ldquo;primitive recursive in.&rdquo; by distinguishing between honest and dishonest classes the classification is related to the computational complexity of the functions classified, and the classification has a wide degree of measure invariance. the structure of the honest and dishonest classes under inclusion is explored. it is shown that any countable partial ordering can be embedded in the honest or in the dishonest classes. the honest classes are dense in themselves, and the dishonest classes are dense in the honest classes. every honest class is minimal over some dishonest class, but there is a dishonest class with no honest class minimal over it. every honest class is the intersection (g.l.b.) of two incomparable honest classes, but there are incomparable pairs of honest classes with no g.l.b. it follows that the upper semi-lattice of the recursive degrees of primitive recursiveness is not a lattice. finally, no r.e. increasing sequence of honest classes has a l.u.b.
a new proof of the weak pigeonhole principle. the exact complexity of the weak pigeonhole principle is an old and fundamental problem in proof complexity. using a diagonalization argument, j. b. paris et al. (j. symbolic logic 53 (1988), 1235-1244) showed how to prove the weak pigeonhole principle with bounded-depth, quasipolynomialsize proofs. their argument was further refined by j. krajícek (j. symbolic logic 59 (1994), 73-86). in this paper, we present a new proof: we show that the weak pigeonhole principle has quasipolynomial-size lk proofs where every formula consists of a single and/or of polylog fan-in. our proof is conceptually simpler than previous arguments, and is optimal with respect to depth.
minimum covers in the relational database model (extended abstract) numerous algorithms concerning relational databases use a cover for a set of functional dependencies as all or part of their input. examples are bernstein and beeri's synthesis algorithm [bb] and the tableau modification algorithm of aho, beeri, and ullman [abu]. the performance of these algorithms may depend both on the number of functional dependencies in the cover and the total size of the cover. starting with a smaller cover will make such algorithms run faster. after bernstein [be75], many researchers believe the problem of finding a minimum cover is np-complete. we show that minimum covers can be found in polynomial time, using the notion of direct determination. the proof details the structure of minimum covers, refining the structure bernstein and beeri show for non-redundant covers [bb]. the kernel algorithm of lewis, sekino, and ting [lst] is improved using these results.
on the angular resolution of planar graphs it is a well-known fact that every planar graph admits a planar straight-line drawing. the angular resolution of such a drawing is the minimum angle subtended by any pair of incident edges. the angular resolution of the graph is the supremum angular resolution over all planar straight-line drawings of the graph. in a recent paper by formann et al. [proc. 31st ieee sympos. on found. of comput. sci., 1990, pp. 86-95], the following question is posed: does there exist a constant $r(d) > 0$ such that every planar graph of maximum degree $d$ has angular resolution $\geq r(d)$ radians? the present authors show that the answer is yes and that it follows easily from results in the literature on disk-packings. the conclusion is that every planar graph of maximum degree $d$ has angular resolution at least $\alpha^d$ radians, $0
byzantine quorum systems. quorum systems are well-known tools for ensuring the consistency and availability of replicated data despite the benign failure of data repositories. in this paper we consider the arbitrary (byzantine) failure of data repositories and present the first study of quorum system requirements and constructions that ensure data availability and consistency despite these failures. we also consider the load associated with our quorum systems, i.e., the minimal access probability of the busiest server. for services subject to arbitrary failures, we demonstrate quorum systems over <i>n</i> servers with a load of <i>o</i>(1/√<i>n</i>), thus meeting the lower bound on load for benignly fault-tolerant quorum systems. we explore several variations of our quorum systems and extend our constructions to cope with arbitrary client failures.
competitive algorithms for on-line problems an on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. examples of on-line problems include scheduling the motion of elevators, finding routes in networks, allocating cache memory, and maintaining dynamic data structures. a competitive algorithm for an on-line problem has the property that its performance on any sequence of requests is within a constant factor of the performance of any other algorithm on the same sequence. this paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.
np-complete decision problems for quadratic polynomials in this article we show the np-completeness of some simple number-theoretic problems. natural simplifications of these problems invariably are known to be in p. our research was motivated by the question whether one could study non-deterministic computation without loss of generality on a restricted, number theoretically significant class of nondeterministic turing machines, the nondeterministic diophantine machines defined below [1,2]. the results suggest this is true. because of the relative difficulty of the reduction of the satisfiability problem used in the proof, and the distinctly number-theoretic character of the problems shown to be np-complete, we hope that the np-completeness of these problems will play a role in showing the np-completeness of further problems of a numerical nature, much as the satisfiability problem has in showing the np-completeness of combinatorial problems ([3],[5]). the results illustrate an intimate connection between problems in computational theory, such as &ldquo;p&equil;np?&rdquo;, and problems in number theory, e.g. about quadratic congruences in one unknown, which are just beyond the range in which efficient algorithms exist. thus our work exposes an interface between the state-of-the-art in number theory and in the theory of computation. also, our results can be seen as the solution to a natural and important revision of hilbert's 10thproblem: give a feasible algorithmic procedure to decide whether an arbitrary diophantine equation has solutions. unless p&equil;np this is impossible, even for a class of quadratic diophantine equations in two unknowns for which a decision procedure in the original sense is in fact available. certainly, these results present a striking rigorous demonstration that number theorists' intuitions about where problems about diophantine equations and quadratic congruences start to be truly difficult are justified.
know thy neighbor's neighbor: the power of lookahead in randomized p2p networks. several peer-to-peer networks are based upon randomized graph topologies that permit efficient greedy routing, e. g., randomized hypercubes, randomized chord, skip-graphs and constructions based upon small-world percolation networks. in each of these networks, a node has out-degree θ(log n), where n denotes the total number of nodes, and greedy routing is known to take o(log n) hops on average. we establish lower-bounds for greedy routing for these networks, and analyze neighbor-of-neighbor (non)-greedy routing. the idea behind non, as the name suggests, is to take a neighbor's neighbors into account for making better routing decisions.the following picture emerges: deterministic routing networks like hypercubes and chord have diameter θ(log n) and greedy routing is optimal. randomized routing networks like randomized hypercubes, randomized chord, and constructions based on small-world percolation networks, have diameter θ(log n / log log n) with high probability. the expected diameter of skip graphs is also θ(log n / log log n). in all of these networks, greedy routing fails to find short routes, requiring ω(log n) hops with high probability. surprisingly, the non-greedy routing algorithm is able to diminish route-lengths to θ(log n / log log n) hops, which is asymptotically optimal.
second-order mathematical theory of computation in this work we show that it is possible to formalize all properties regularly observed in (deterministic and non-deterministic) algorithms in second-order predicate calculus. moreover, we show that for any given algorithm it suffices to know how to formalize its 'partial correctness' by a second-order formula in order to formalize all other properties by second-order formulas. this result is of special interest since 'partial correctness' has already been formalized in second-order predicate calculus for many classes of algorithms.
formalization of properties of recursively defined functions this paper is concerned with the relationship between the convergence, correctness and equivalence of recursively defined functions and the satisfiability (or unsatisfiability) of certain first-order formulas.
the optimal fixedpoint of recursive programs in this paper a new fixedpoint approach towards the semantics of recursive programs is presented. the fixedpoint defined by a recursive program under this semantics contains, in some sense, the maximal amount of &ldquo;interesting&rdquo; information which can be extracted from the program. this optimal fixedpoint (which always uniquely exists) may be strictly more defined than the program's least fixedpoint. we consider both the theoretical and the computational aspects of the approach, as well as some techniques for proving properties of the optimal fixedpoint of a given recursive program.
on syntax-directed transduction and tree transducers several topics of theoretical and practical importance to the field of translator writing systems are presented in this paper. these are (1). implementation of generalized syntax-directed transduction (gsdt) on a finite-state tree transducer; (2). implementation of gsdt on a tree-walking pushdown store transducer; (3). transformation of the context-free grammar underlying a gsdt and the resulting transformation of the transduction elements of that gsdt; (4). tree transduction of parse trees between equivalent context-free grammars.
the price of selfish routing. we study the problem of routing traffic through a congested network. we focus on the simplest case of a network consisting of m parallel links. we assume a collection of n network users, each employing a mixed strategy which is a probability distribution over links, to control the shipping of its own assigned traffic. given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum expected latency over all links is minimized. we consider both uniform and non-uniform link capacities.how much decrease in global performace is necessary due to the absence of some central authority to regulate network traffic and implement an optimal assignment of traffic to links? we investigate this fundamental question in the context of nash equilibria for such a system, where each network user selfishly routes its traffic only on those links available to it that minimize its expected latency cost, given the network congestion caused by the other users. we use the coordination ratio, defined by koutsoupias and papadimitriou [25] as the ratio of the maximum (over all links) expected latency in the worst possible nash equlibrium, over the least possible maximum latency had global regulation been available, as a measure of the cost of lack of coordination among the network users.
self-stabilizing symmetry breaking in constant-space (extended abstract) we investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bidirectional ring of identical processors, where each processor is an asynchronous probabilistic (coin-flipping) finite state machine which sends and receives messages. we show that the solution to this problem is equivalent to symmetry breaking (i.e., leader election). requiring only constant-size messages and message-passing model has practical implications: our solution can be implemented in high-speed networks using a universal fast hardware switches (i.e., finite state machines) of size independent of the size of the network.
an algorithm for the general petri net reachability problem an algorithm is presented for the general petri net reachability problem based on a generalization of the basic reachability construction which is symmetric with respect to the initial and final marking. sets of transition sequences described by finite automata are used for approximations to firing sequences, and the approximation error is assessed by uniformly constructable presburger expressions. the approximation algorithm is iterated until a sufficient criterion for reachability can be given, not-withstanding the remaining uncertainty.
classes of computable functions defined by bounds on computation: preliminary report the structure of the functions computable in time or space bounded by t is investigated for recursive functions t. the t-computable classes are shown to be closed under increasing recursively enumerable unions; as a corollary the primitive recursive functions are shown to equal the t-computable functions for a certain recursive t. any countable partial order can be isomorphically embedded in the family of t-computable classes partially ordered by set inclusion. for any recursive t, there is a recursive t' which is (approximately) equal to an actual running time such that the t-computable functions equal the t'-computable functions.
the correctness of a modified secd machine landin's secd machine does not completely compute certain expressions of the &lgr;-calculus and so is modified by the addition of an output component and a unique name counter. this modified machine is proven to correctly implement the &lgr;-calculus.
a decision procedure for generalized sequential mapability-onto of regular sets in [1] various problems are solved about the possibility of mapping regular sets into or onto other regular sets by means of a complete sequential machine or a generalized sequential machine under various restraints. one problem in this class has remained open. that problem, as restated on pp. 129-130 of [2], is whether it is &ldquo;recursively solvable to determine for arbitrary regular sets l1 and l2 whether there exists a generalized sequential machine s such that s(l1) &equil; l2.&rdquo; the claim is hereby made on the affirmative solution to this problem. [3] contains an interesting solution to a certain nontrivial subproblem, namely where l1 and l2 are restricted to regular sets with the prefix property.
combinatorial optimization with rational objective functions let a be the problem of minimizing c1x1+...+cnxn subject to certain constraints on x&equil;(x1,...,xn), and let b be the problem of minimizing (a0+a1x1+...+anxn)/(b0+b1x1+...+bnxn) subject to the same constraints, assuming the denominator is always positive. it is shown that if a is solvable within o[p(n)] comparisons and o[q(n)] additions, then b is solvable in time o[p(n)(q(n)+p(n))]. this applies to most of the &ldquo;network&rdquo; algorithms. consequently, minimum ratio cycles, minimum ratio spanning trees, minimum ratio (simple) paths, maximum ratio weighted matchings, etc., can be computed within polynomial-time in the number of variables. this improves a result of e. l. lawler, namely, that a minimum ratio cycle can be computed within a time bound which is polynomial in the number of bits required to specify an instance of the problem. a recent result on minimum ratio spanning trees by r. chandrasekaran is also improved by the general arguments presented in this paper. algorithms of time-complexity o(&brvbar;e&brvbar; &bull; &brvbar;v&brvbar;2&bull;log&brvbar;v&brvbar;) for a minimum ratio cycle and o(&brvbar;e&brvbar; &bull; log2&brvbar;v&brvbar; &bull; log log &brvbar;v&brvbar;) for a minimum ratio spanning tree are developed.
polynomial and abstract subrecursive classes we define polynomial time computable operator. our definition generalizes cook's definition to arbitrary function inputs. polynomial classes are defined in terms of these operators; the properties of these classes are investigated. honest polynomial classes are generated by running time. they posses a modified ritchie-cobham property. a polynomial class is a complexity class iff it is honest. starting from the observation that many results about subrecursive classes hold for all reducibility relations (e.g. primitive recursive in, elementary recursive in), which were studied so far, we define abstract subrecursive reducibility relation. many results hold for all abstract subrecursive reducibilities.
las vegas is better than determinism in vlsi and distributed computing (extended abstract) in this paper we describe a new method for proving lower bounds on the complexity of vlsi - computations and more generally distributed computations. lipton and sedgewick observed that the crossing sequence arguments used to prove lower bounds in vlsi (or tm or distributed computing) apply to (accepting) nondeterministic computations as well as to deterministic computations. hence whenever a boolean function f is such that f and -&-fmarc; (the complement of f, -&-fmarc; -&-equil; 1 -&-minus; f) have efficient nondeterministic chips then the known techniques are of no help for proving lower bounds on the complexity of deterministic chips. in this paper we describe a lower bound technique (thm 1) which only applies to deterministic computations
program size and economy of descriptions: preliminary report restricted programming languages, for example primitive recursive definition schemes, are very often not nearly as succinct in describing primitive recursive functions as a general programming language [1]. we show that as one increases the power of programming languages, one can obtain economies in program size by any recursive amount for even very simple functions. this parallels a situation in the arithmetic hierarchy, where it is possible to get a recursively enumerable set whose smallest recursively enumerable index is much larger than the smallest index for the same set considered, say, as a set recursively enumerable in &oslash;'. these phenomena follow from the fact that the ability to write programs which refer to the universal functions of an enumeration enables one to decrease significantly the size of programs. the notation, when not defined is that of [4].
definability in dynamic logic we study the expressive power of various versions of dynamic logic and compare them with each other as well as with standard languages in the logical literature. one version of dynamic logic is equivalent to the infinitary logic lck&ohgr;1&ohgr;, but regular dynamic logic is strictly less expressive. in particular, the ordinals &ohgr;&ohgr; and &ohgr; &ohgr;.2 are indistinguishable by formulas of regular dynamic logic.
on the expressive power of dynamic logic (preliminary report) we show that &ldquo;looping&rdquo; of while-programs can be expressed in regular first-order dynamic logic, disproving a conjecture made in [harel-pratt 1978]. in addition we show that the expressive power of quantifier-free dynamic logic increases when nondeterminism is introduced in the programs that are part of formulae of dynamic logic. allowing assignments of random values to variables increases the expressive power even further.
linear representation of tree structure: a mathematical theory of parenthesis-free notations in this paper we present a substantially general theory of parenthesis-free notations for finite plane trees. we obtain stronger one-to-oneness results, including a characterization of one-to-oneness for a large class of notations, and a quite general sufficient condition for one-to-oneness that involves the recursive structure of plane trees in what appears to be a minimal way. we then study various properties of notations that promise to be of practical interest. the two most important of these&mdash;single scan bottom-up readability, and single scan top-down readability&mdash;both turn out to be particular cases of our general sufficient condition for one-to-oneness. we formulate simple descriptions of all notations that have one or the other of these properties, and find a simple transformation of notations that establishes a one-to-one correspondence between them. the unique fixed point of this transformation turns out to be the only notation single scan readable in both directions.
profit-earning facility location. we consider opening facilities in order to gain a profit. we are given a set of demand points, and we must open some set of facilities such that every demand may be satisfied from a local facility and the total profit gained in this process is maximized. this contrasts with previous work on facility location and k-center problems, where opening a facility incurred a cost. the profit gained by opening a facility is a function of the amount of demand the facility satisfies. we model the dependence of profit on demand by creating many different possible facilities at each location, each of which provides a certain profit if opened and requires at least a certain amount of demand in order to open. our model captures problem instances where profits may be positive or negative, and also instances where it is not necessary to satisfy every demand. our algorithms provide the optimum total profit, while stretching the definition of locality by a constant and violating the required demands by a constant. we prove that without this stretch, the problem becomes np-hard to approximate.