waashk/dblp huggingface dataset:
super-tasks, accelerating turing machines and uncomputability. accelerating turing machines are devices with the same computational structure as turing machines (tm), but able to perform super-tasks. we ask whether performing super-tasks alone produces more computational power; for example, whether accelerating tm can solve the halting problem. we conclude that this is not the case. no accelerating tm solves the halting problem. the argument rests on an analysis of the reasoning that leads to thomson's paradox. the key point is that the paradox rests on a conflation of different perspectives of accelerating processes. this leads to concluding that the same conflation underlies the claim that accelerating tm can solve the halting problem.
on two-sided infinite fixed points of morphisms. let &sgr; be a finite alphabet, and let h:&sgr;*&sgr; be a morphism. finite and infinite fixed points of morphismsi.e., those words w such that h(w)=wplay an important role in formal language theory. head characterized the finite fixed points of h, and later, head and lando characterized the one-sided infinite fixed points of h. our paper has two main results. first, we complete the characterization of fixed points of morphisms by describing all two-sided infinite fixed points of h, for both the "pointed" and "unpointed" cases. second, we completely characterize the solutions to the equation h(xy)=yx in finite words.
on viewing block codes as finite automata. block codes are viewed from a formal language theoretic perspective. it is shown that properties of trellises for subclasses of block codes called rectangular codes follow naturally from the myhill nerode theorem. a technique termed subtrellis overlaying is introduced with the object of reducing decoder complexity. necessary and sufficient conditions for trellis overlaying are derived from the representation of the block code as a group, partitioned into a subgroup and its cosets. the conditions turn out to be simple constraints on coset leaders. it is seen that overlayed trellises are tail-biting trellises for which decoding is generally more efficient than that for conventional trellises. finally, a decoding algorithm for tail-biting trellises is described, and the results of some simulations are presented.
bijections and the riordan group. one of the cornerstone ideas in mathematics is to take a problem and to look at it in a bigger space. in this paper we examine combinatorial sequences in the context of the riordan group. various subgroups of the riordan group each give us a different view of the original sequence. in many cases this leads to both a combinatorial interpretation and to eco rewriting rules. in this paper we will concentrate on just four of the subgroups of the riordan group to demonstrate some of the possibilities of this approach.
logical operations and kolmogorov complexity. conditional kolmogorov complexity k(x|y) can be understood as the complexity of the problem "y&rarr;x", where x is the problem "construct x" and y is the problem "construct y". other logical operations (&uarr;, &darr;, &harr;) can be interpreted in a similar way, extending kolmogorov interpretation of intuitionistic logic and kleene realizability. this leads to interesting problems in algorithmic information theory. some of these questions are discussed.
loop checks for logic programs with functions. two complete loop checking mechanisms have been presented in the literature for logic programs with functions: os-check and eva-check. os-check is computationally efficient but quite unreliable in that it often misidentifies infinite loops, whereas eva-check is reliable for a majority of cases but quite expensive. in this paper, we develop a series of new complete loop checking mechanisms, called vaf-checks. the key technique we introduce is the notion of expanded variants, which captures a key structural characteristic of in finite loops. we show that our approach is superior to both os-check and eva-check in that it is as efficient as os-check and as reliable as eva-check. copyright 2001 elsevier science b.v.
2-role assignments on triangulated graphs. if g is a graph, a k-role assignment is a function mapping each vertex into a role, a positive integer 1, 2,...,k, so that if x and y have the same role, then the sets of roles assigned to their neighbors are the same. a graph is called a triangulated graph if it contains no chord-less cycle of four or more vertices. one interesting type of triangulated graph is the indifference graph, that is a graph for which we can find a function on its vertex set so that if x and y are adjacent, then their assigned function values are close. we study 2-role assignments for triangulated graphs. we provide a "greedy" algorithm for finding a 2-role assignment on a connected, nonbipartite triangulated graph with at most one pendant vertex. we characterize indifference graphs that have a 2-role assignment.
edge-colouring of join graphs. a join graph is the complete union of two arbitrary graphs. we give sufficient conditions for a join graph to be 1-factorizable. as a consequence of our results, the hilton's overfull subgraph conjecture holds true for several subclasses of join graphs.
asymptotically optimal declustering schemes for 2-dim range queries. declustering techniques have been widely adopted in parallel storage systems (e.g. disk arrays) to speed up bulk retrieval of multidimensional data. a declustering scheme distributes data items among multiple disks, thus enabling parallel data access and reducing query response time. we measure the performance of any declustering scheme as its worst case additive deviation from the ideal scheme. the goal thus is to design declustering schemes with as small an additive error as possible. we describe a number of declustering schemes with additive error o(log m) for 2-dimensional range queries, where m is the number of disks. these are the first results giving o(logm) upper bound for all values of m. our second result is a lower bound on the additive error. it is known that except for a few stringent cases, additive error of any 2-dimensional declustering scheme is at least one. we strengthen this lower bound to ω((logm)(d-1/2)) for d-dimensional schemes and to ω(logm) for 2-dimensional schemes, thus proving that the 2-dimensional schemes described in this paper are (asymptotically) optimal. these results are obtained by establishing a connection to geometric discrepancy. we also present simulation results to evaluate the performance of these schemes in practice.
on a monadic semantics for freshness. a standard monad of continuations, when constructed with domains in the world of fm-sets [m.j. gabbay, a.m. pitts, a new approach to abstract syntax with variable binding, formal aspects comput. 13 (2002) 341-363], is shown to provide a model of dynamic allocation of fresh names that is both simple and useful. in particular, it is used to prove that the powerful facilities for manipulating fresh names and binding operations provided by the "fresh" series of metalanguages [m.r. shinwell, swapping the atom: programming with binders in fresh o'caml, proc. merλin, 2003; m.r. shinwell, a.m. pitts, fresh o'caml user manual, cambridge university computer laboratory, september 2003, available at 〈http://www.freshml.org/foc/〉 m.r. shinwell, a.m. pitts, m.j. gabbay, freshml: programming with binders made simple, in: proc. icfp '03, acm press, 2003, pp. 263-274] respect α-equivalence of object-level languages up to meta-level contextual equivalence.
finite-state analysis of two contract signing protocols. optimistic contract signing protocols allow two parties to commit to a previously agreed upon contract, relying on a third party to abort or confirm the contract if needed. these protocols are relatively subtle, since there may be interactions between the subprotocols used for normal signing without the third party, aborting the protocol through the third party, or requesting confirmation from the third party. with the help of mur, a finite-state verification tool, we analyze two related contract signing protocols: the optimistic contract signing protocol of asokan, shoup, and waidner, and the abuse-free contract signing protocol of garay, jakobsson, and mackenzie. for the first protocol, we discover that a malicious participant can produce inconsistent versions of the contract or mount a replay attack. for the second protocol, we discover that negligence or corruption of the trusted third party may allow abuse or unfairness. in this case, contrary to the intent of the protocol, the cheated party is not able to hold the third party accountable. we present and analyze modifications to the protocols that avoid these problems and discuss the basic challenges involved in formal analysis of fair exchange protocols.
non-cooperative computation: boolean functions with correctness and exclusivity. we introduce the concept of non-cooperative computation (ncc), which is the joint computation of a function by self-motivated agents, where each of the agents possesses one of the inputs to the function. in ncc the agents communicate their input (truthfully or not) to a trusted center, which performs a commonly-known computation and distributes the results to the agents. the question is whether the agents can be incented to communicate their true input to the center, allowing all agents to compute the function correctly. ncc is a game theoretic concept and specifically is couched in terms of mechanism design. ncc is a very broad framework and is specialized by imposing specific structure on the agents' utility functions. the technical results we present are specific to the setting in which each agent has a primary interest in computing the function and a secondary interest in preventing the others from computing it (properties called correctness and exclusivity). for this setting we provide a complete characterization of the boolean functions that are non-cooperatively computable. we do this for three versions of ncc: a basic deterministic version, a probabilistic version and a version in which the computation can be subsidized by the center. the analysis turns out to depend on whether the inputs of the agents are probabilistically correlated or not and we analyze both cases.
correlation immunity and resiliency of symmetric boolean functions. correlation immunity of symmetric boolean functions is studied in this paper. lower bounds on the number of constructible correlation immune symmetric functions are given. constructions for such new balanced functions are presented. these functions are also known as 1-resilient functions. in 1985, chor et al. conjectured that the only 1-resilient symmetric functions are the exclusive-or of all n variables and its negation. this conjecture, however, was disproved by gopalakrishnan, hoffman and stinson in 1993 by giving a class of infinite counterexamples, and they noted that it does not seem to extend any further in an obvious way. in this paper two more infinite classes of such examples are presented for n being even and being odd, respectively, and consequently one of the two open problems proposed by gopalakrishnan et al., is addressed by constructing new symmetric resilient functions.
faster deterministic sorting through better sampling. in this paper, a refined deterministic sampling strategy is presented. it allows to improve the performance of deterministic sample-sort algorithms to the point that they can compete with their randomized counterparts. the method is illustrated by a detailed analysis for the cases of sorting on meshes and for sorting in external memory on a single processor machine.
faster gossiping on butterfly networks. gossiping has been considered intensively for butterflies and "simple" butterflies (which have no wrap-around connections). in the "telephone" communication model, for a butterfly of order k, the best previous gossiping algorithms require 2½k and 3k communication rounds, respectively. by new asymptotic methods we break through these bounds. we show that gossiping on a class of "column-based" networks, which also contains the cube-connected cycles, can be reduced to the simpler problem of "row-gossiping". row-gossiping in turn is reduced to "coherent row-broadcasting". this latter problem is sufficiently simple to be solved by a sophisticated computer program for butterflies with up to 15 × 215 nodes. out of the produced solutions a pattern is distilled, which can be used to perform gossiping on butterflies and simple butterflies of order k in 21/4k + o(k) and 2½k + o(k) rounds, respectively, for any k, considerably reducing the gap with the lower bounds. the new upper bounds also hold for gossiping in the weaker "telegraph" model.
endgame problems of sim-like graph ramsey avoidance games are pspace-complete. in sim, two players compete on a complete graph of six vertices (k6). the players alternate in coloring one as yet uncolored edge using their color. the player who first completes a monochromatic triangle (k3) loses. replacing k6 and k3 by arbitrary graphs generalizes sim to graph ramsey avoidance games. given an endgame position in these games, the problem of deciding whether the player who moves next has a winning strategy is shown to be pspace-complete. it can be reduced from the problem of whether the first player has a winning strategy in the game gpos(pos cnf) (schacfer, j. comput. system sci. 16 (2) (1978) 185-225). the following game variants are also shown to have pspace-complete endgame problems: (1) completing a monochromatic subgraph isomorphic to a is forbidden and the player who is first unable to move loses, (2) both players are allowed to color one or more edges in each move, (3) more than two players take part in the game, and (4) each player has to avoid a separate graph. in all results, the graphs to be avoided can be restricted to the bowtie graph (⋈, i.e., two triangles with one common vertex).
geometrical semantics for linear logic (multiplicative fragment). linear logic was described by girard as a logic of dynamic interactions. on the other hand, girard suggested an analogy between ll and quantum theory. following these two intuitions we give an interpretation of linear logic in the language, which is common for both dynamical systems and quantization. thus, we propose a denotational semantics for multiplicative linear logic using the language of symplectic geometry.we construct a category of coherent phase spaces and show that this category provides a model for mll. a coherent phase space is a pair: a symplectic manifold and a distinguished field of contact cones on this manifold. the category of coherent phase spaces is a refinement of the symplectic "category" introduced by weinstein. a morphism between two coherent phase spaces is a lagrangian submanifold of their product, which is tangent to some distinguished field of contact cones. thus, we interpret formulas of mll as fields of contact cones on symplectic manifolds, and proofs as integral submanifolds of corresponding fields.in geometric and asymptotic quantization symplectic manifolds are phase spaces of classical systems, and lagrangian submanifolds represent asymptotically states of quantized systems. typically, a lagrangian submanifold is the best possible localization of a quantum system in the classical phase space, as follows from the heisenberg uncertainty principle. lagrangian submanifolds are called sometimes "quantum points".from this point of view we interpret linear logic proofs as (geometric approximations to) quantum states and formulas as specifications for these states. in particular, the interpretation of linear negation suggests that the dual formulas a and a⊥ stand in the same relationship as the position and momentum observables. these two observables cannot simultaneously have definite values, much like the case of two dual formulas, which cannot simultaneously have proofs.
the homomorphism problem for trace monoids. it is proved to be decidable, for any given finite subset f of x*, dependency alphabet (y, τ) and mapping φ : f → y*, whether or not φ can be extended to a monoid homomorphism φ : f* → m(y,τ). this contrasts with the undecidability of the symmetric problem, when we consider the dependency alphabet (x, τ) instead. some other particular cases of homomorphism and isomorphism problems among trace monoids are also discussed.
constructing an asymptotic phase transition in random binary constraint satisfaction problems. the standard models used to generate random binary constraint satisfaction problems are described. at the problem sizes studied experimentally, a phase transition is seen as the constraint tightness is varied. however, achlioptas et al. showed that if the problem size (number of variables) increases while the remaining parameters are kept constant, asymptotically almost all instances are unsatisfiable. in this paper, an alternative scheme for one of the standard models is proposed in which both the number of values in each variable's domain and the average degree of the constraint graph are increased with problem size. it is shown that with this scheme there is asymptotically a range of values of the constraint tightness in which instances are trivially satis-able with probability at least 0.5 and a range in which instances are almost all unsatisfiable; hence there is a crossover point at some value of the constraint tightness between these two ranges. this scheme is compared to a similar scheme due to xu and li.
extensions and submonoids of automatic monoids. in this paper, submonoids and extensions of automatic and p-automatic monoids are studied. the concept of a p-automatic monoid is a variant on the usual concept of an automatic monoid designed to allow a geometric characterization analogous to the group case. in the case of right cancellative monoids, the two concepts coincide. here, we study rational submonoids of (p-)automatic monoids, being able to show in many cases that (p-)automaticity is inherited. our sharpest results concern rational subgroups. also, closure properties are established for various notions of extensions of (p-)automatic monoids, including different types of products, ideal extensions, and rees matrix constructions.
a linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations. in this paper, we consider a transformation on binary trees using new types of rotations. each of the newly proposed rotations is permitted only at nodes on the left-arm or the fight-arm of a tree. consequently, we develop a linear time algorithm with at most n - 1 rotations for converting weight sequences between any two binary trees. in particular, from an analysis of aggregate method for a sequence of rotations, each rotation of the proposed algorithm can be performed in a constant amortized time. next, we show that a specific directed rooted tree called rotation tree can be constructed using one of the new type rotations. as a by-product, a naive algorithm for enumerating weight sequences of binary trees in lexicographic order can be implemented by traversing the rotation tree.
an analysis of the lpt algorithm for the max-min and the min-ratio partition problems. given a set of positive numbers, the max-min partition problem asks for a k-partition such that the minimum part is maximized. the min-ratio partition problem has the similar definition but the objective is to minimize the ratio of the maximum to the minimum parts. in this paper, we analyze the performances of the longest processing time (lpt) algorithm for the two problems. we show that the tight bounds of the lpt are, respectively (4k - 2)/(3k - 1) and 7/5.
new results of exhaustive search in the game amazons. amazons is a young, abstract, strategic, two-player game, in which the first player unable to move loses. we present a database for small amazons positions, which for every position holds the canonical combinatorial game theory values, its thermograph and the corresponding move for every canonical option.such a database is useful to find values and structures in games that were unknown before and hard or impossible to find or verify by hand. in amazons we were able to prove the existence of numbers, of fractions down to 1/64 and of various infinitesimals, but these results also suggest that there is no easy construction for most of these values. the database also demonstrates how complex canonical forms in amazons can be and that many amazons positions have properties and values that are totally counterintuitive.
the computational power of benenson automata. the development of autonomous molecular computers capable of making independent decisions in vivo regarding local drug administration may revolutionize medical science. recently benenson et al. [an autonomous molecular computer for logical control of gene expression, nature 429 (2004) 423-429.] have envisioned one form such a "smart drug" may take by implementing an in vitro scheme, in which a long dna state molecule is cut repeatedly by a restriction enzyme in a manner dependent upon the presence of particular short dna "rule molecules." to analyze the potential of their scheme in terms of the kinds of computations it can perform, we study an abstraction assuming that a certain class of restriction enzymes is available and reactions occur without error. we also discuss how our molecular algorithms could perform with known restriction enzymes. by exhibiting a way to simulate arbitrary circuits, we show that these "benenson automata" are capable of computing arbitrary boolean functions. further, we show that they are able to compute efficiently exactly those functions computable by log-depth circuits. computationally, we formalize a new variant of limited width branching programs with a molecular implementation.
on categorical equivalence of gentzen-style derivations in imll. a new deciding algorithm for categorical equivalence of derivations in intuitionistic multiplicative linear logic (imll) is proposed. the algorithm is based uniquely on manipulations with gentzen-style derivations. the algorithm has low polynomial complexity. the paper also contains results concerning permutability of rules and its connection with categorical equivalence.
numerical factorization of multivariate complex polynomials. one can consider the problem of factoring multivariate complex polynomials as a special case of the decomposition of a pure dimensional solution set of a polynomial system into irreducible components. the importance and nature of this problem however justify a special treatment. we exploit the reduction to the univariate root finding problem as a way to sample the polynomial more efficiently, certify the decomposition with linear traces, and apply interpolation techniques to construct the irreducible factors. with a random combination of differentials we lower multiplicities and reduce to the regular case. estimates on the location of the zeroes of the derivative of polynomials provide bounds on the required precision. we apply our software to study the singularities of stewart-gough platforms.
universal computation with watson-crick d0l systems. watson-crick d0l systems, introduced in 1997 by mihalache and salomaa, arise from two major principles: the lindenmayer rewriting and the watson-crick complementarity principle. complementarity can be viewed as a purely language-theoretic operation. majority of a certain type of symbols in a string (purines vs. pyrimidines) triggers a transition to the complementary string. the paper deals with an expressive power of deterministic interactionless watson-crick lindenmayer systems. a rather surprising result is obtained: these systems, consisting of iterated morphism and a basic dna operation, are able to compute any turing computable function.