waashk/dblp huggingface dataset:
entropy as a fixed point. we study complexity and information and introduce the idea that while complexity is relative to a given class of processes, information is process independent: information is complexity relative to the class of all conceivable processes. in essence, the idea is that information is an extension of the concept 'algorithmic complexity' from a class of desirable and concrete processes, such as those represented by binary decision trees, to a class more general that can only in pragmatic terms be regarded as existing in the conception. it is then precisely the fact that information is defined relative to such a large class of processes that it becomes an effective tool for analyzing phenomena in a wide range of disciplines.we test these ideas on the complexity of classical states. a domain is used to specify the class of processes, and both qualitative and quantitative notions of complexity for classical states emerge. the resulting theory is used to give new proofs of fundamental results from classical information theory, to give a new characterization of entropy in quantum mechanics, to establish a rigorous connection between entanglement transformation and computation, and to derive lower bounds on algorithmic complexity. all of this is a consequence of the setting which gives rise to the fixed point theorem: the least fixed point of the copying operator above complexity is information.
()-arbiters for -out-of- mutual exclusion problem. h-out-of-k mutual exclusion is a generalization of the 1-mutual exclusion problem, where there are k units of shared resources and each process requests h (1 ≤ h ≤ k) units at the same time. though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for 1-mutual exclusion. thus, the algorithm based on k-arbiter needs many messages. this paper introduces the new notion that each request uses different quorums depending on the number of units of its request. based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k + 1)-cube (h,k)-arbiter. the quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. a uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. a (k + 1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion.
measuring the probabilistic powerdomain. in this paper we initiate the study of measurements on the probabilistic powerdomain. we show how measurements on an underlying domain naturally extend to its probabilistic powerdomain, so that the kernel of the extension consists of exactly those normalized measures on the kernel of the measurement on the underlying domain. this result is combined with now-standard results from the theory of measurements to obtain a new proof that the fixed point associated with a weakly hyperbolic ifs with probabilities is the unique invariant measure whose support is the attractor of the underlying ifs.
learning power and language expressiveness. the topic of the present work is to study the relationship between the power of the learning algorithms on the one hand, and the expressive power of the logical language which is used to represent the problems to be learned on the other hand. the central question is whether enriching the language results in more learning power. in order to make the question relevant and nontrivial, it is required that both texts (sequences of data) and hypotheses (guesses) be translatable from the "rich" language into the "poor" one. the issue is considered for several logical languages suitable to describe structures whose domain is the set of natural numbers. it is shown that enriching the language does not give any advantage for those languages which define a monadic second-order language being decidable in the following sense: there is a fixed interpretation in the structure of natural numbers such that the set of sentences of this extended language true in that structure is decidable. but enriching the original language even by only one constant gives an advantage if this language contains a binary function symbol (which will be interpreted as addition). furthermore, it is shown that behaviourally correct learning has exactly the same power as learning in the limit for those languages which define a monadic second-order language with the property given above, but has more power in case of languages containing a binary function symbol. adding the natural requirement that the set of all structures to be learned is recursively enumerable, it is shown that it pays off to enrich the language of arithmetics for both finite learning and learning in the limit, but it does not pay off to enrich the language for behaviourally correct learning.
unifying logic, topology and learning in parametric logic. many connections have been established between learning and logic, or learning and topology, or logic and topology. still, the connections are not at the heart of these fields. each of them is fairly independent of the others when attention is restricted to basic notions and main results. we show that connections can actually be made at a fundamental level, and result in a logic with parameters that needs topological notions for its early developments, and notions from learning theory for interpretation and applicability.one of the key properties of first-order logic is that the classical notion of logical consequence is compact. we generalize the notion of logical consequence, and we generalize compactness to β-weak compactness where β is an ordinal. the effect is to stratify the set of generalized logical consequences of a theory into levels, and levels into layers. deduction corresponds to the lower layer of the first level above the underlying theory, learning with less than β mind changes to layer β of the first level, and learning in the limit to the first layer of the second level. refinements of borel-like hierarchies provide the topological tools needed to develop the framework.
analysis of security protocols as open systems. we propose a methodology for the formal analysis of security protocols. this originates from the observation that the verification of security protocols can be conveniently treated as the verification of open systems, i.e. systems which may have unspecified components. these might be used to represent a hostile environment wherein the protocol runs and whose behavior cannot be predicted a priori. we define a language for the description of security protocols, namely crypto-ccs, and a logical language for expressing their properties. we provide an effective verification method for security protocols which is based on a suitable extension of partial model checking. indeed, we obtain a decidability result for the secrecy analysis of protocols with a finite number of sessions, bounded message size and new nonce generation.
boolean restriction categories and taut monads. a boolean category is a restriction category if and only if it has one exception and all morphisms are deterministic. in the category of sets, taut monads are precisely the boolean ones. it follows that collection monad types in haskell inherit an assertion calculus based on dynamic logic.
efficient iteration in admissible combinatorial classes. the exhaustive generation of combinatorial objects has a vast range of practical applications and is a common theme in the combinatorial research field. but most previous works in this area concentrate in the efficient generation of particular families of combinatorial objects. the novel approach of the work presented here is to provide efficient generic algorithms, where the input is not just the size n of the objects to be generated but a finite specification of the combinatorial class whose objects we want to list. since the algorithms are generic, they do not exploit any particular feature of the class to be generated; nevertheless, they work in constant amortized time per generated object, that is, they generate all n objects of a given size in θ(n) time. these algorithms are useful for both rapid prototyping and for inclusion into general purposes libraries because of their flexibility, with only a relatively modest penalty on efficiency. furthermore, the framework presented in this paper nicely combines with the framework developed by flajolet et al. for the enumeration and random generation of combinatorial objects, and with the framework developed by the authors for the unranking of combinatorial objects.
hard variants of stable marriage. the stable marriage problem and its many variants have been widely studied in the literature (gusfield and irving, the stable marriage problem: structure and algorithms, mit press, cambridge, ma, 1989; roth and sotomayor, two-sided matching: a study in game-theoretic modeling and analysis, econometric society monographs, vol. 18, cambridge university press, cambridge, 1990; knuth, stable marriage and its relation to other combinatorial problems, crm proceedings and lecture notes, vol. 10, american mathematical society, providence, ri, 1997), partly because of the inherent appeal of the problem, partly because of the elegance of the associated structures and algorithms, and partly because of important practical applications, such as the national resident matching program (roth, j. political economy 92(6) (1984) 991) and similar large-scale matching schemes. here, we present the first comprehensive study of variants of the problem in which the preference lists of the participants are not necessarily complete and not necessarily totally ordered. we show that, under surprisingly restrictive assumptions, a number of these variants are hard, and hard to approximate. the key observation is that, in contrast to the case where preference lists are complete or strictly ordered (or both), a given problem instance may admit stable matchings of different sizes. in this setting, examples of problems that are hard are: finding a stable matching of maximum or minimum size, determining whether a given pair is stableeven if the indifference takes the form of ties on one side only, the ties are at the tails of lists, there is at most one tie per list, and each tie is of length 2; and finding, or approximating, both an `egalitarian' and a `minimum regret' stable matching. however, we give a 2-approximation algorithm for the problems of finding a stable matching of maximum or minimum size. we also discuss the significant implications of our results for practical matching schemes.
the convergence of functions to fixedpoints of recursive definitions. the classical method for constructing the least fixedpoint of a recursive definition is to generate a sequence of functions whose initial element is the totally undefined function and which converges to the desired least fixedpoint. this method, due to kleene, cannot be generalized to allow the construction of other fixedpoints. in this paper we present an alternate definition of convergence and a new fixedpoint access method of generating sequences of functions for a given recursive definition. the initial function of the sequence can be an arbitrary function, and the sequence will always converge to a fixedpoint that is "close" to the initial function. this defines a monotonic mapping from the set of partial functions onto the set of all fixedpoints of the given recursive definition.
some results on hahn-banach-type theorems for continuous d-cones. like the extended non-negative reals r+ equipped with the scott topology, there are other real topological cones such that the specialisation order yields a directed complete partially ordered set (dcpo). we will call them d-cones. further examples are the extended probabilistic powerdomain, the set of all lower semicontinuous functions f : x ->r+ for any topological space x and arbitrary products of given d-cones. the dual cone c* for a given d-cone c consists of all linear continuous functions &lgr; :c -> r+. with respect to the pointwise order, addition and scalar multiplication the dual cone becomes also a d-cone. we are interested in obtaining results with our concept of d-cones that are comparable to hahn-banach-type theorems in functional analysis. indeed, we can prove an extension theorem and a separation theorem for the continuous d-cones. in particular, the second implies that the elements of the dual cone c* separate the points of c. as a consequence of the extension theorem, we obtain a sum theorem for continuous d-cones. we will give some suffcient conditions when the previous examples of d-cones are continuous and have an additive way-below relation
ramsey numbers for tournaments. the ramsey number r(d1,...,dk) of acyclic directed graphs d1,...,dk is defined as the largest integer r for which there exists a tournament t = (v, a) on r vertices with a k-coloring &fgr; : a &rarr; {1,...,k} of the are set a such that no dt occurs in color i for any i &egr; {1,...,k} . we discuss recursive techniques to compute r(d1,...,dk) in the case where there are paths and/or stars among the dr in particular, solving a problem of bialostocki and dierker [congr. numer. 47 (1985) 119-123], we prove that r(d1d2)= r(d1)&bull;r(d2)holds if dt is transistive and d2 = sn is an out-going star on n vertices. our main result is an asymptotic formula for r(d1,...,d1, sn) where the digraphs d1,..., dk are fixed arbitrarily and n&rarr;(infinity sign).
parameterized graph separation problems. we consider parameterized problems where some separation property has to be achieved by deleting as few vertices as possible. the following five problems are studied: delete k vertices such that (a) each of the given l terminals is separated from the others, (b) each of the given l pairs of terminals is separated, (c) exactly l vertices are cut away from the graph, (d) exactly l connected vertices are cut away from the graph, (e) the graph is separated into at least l components. we show that if both k and l are parameters, then (a), (b) and (d) are fixed-parameter tractable, while (c) and (e) are w[1]-hard.
codes and equations on trees. the objective of this paper is to study, by new formal methods, the notion of tree code introduced by m. nivat in \cite{n92}. in particular we introduce the notion of stability for sets of trees closed under concatenation. this allows us to give a characterization of tree codes which is very close to the algebraic characterization of word codes in terms of free monoids. we further define the stable hull of a set of trees and derive a defect theorem for trees, which generalizes the analogous result for words. as a consequence we obtain some properties of tree codes having two elements. moreover we propose a new algorithm to test whether a finite set of trees is a tree code. the running time of the algorithm is polynomial in the size of the input. we also introduce the notion of tree equation as a complementary point of view to tree codes. the main problem emerging in this approach is to decide the satisfiability of tree equations: it is a special case of second order unification, and it remains still open.
parameterized coloring problems on chordal graphs. in the precoloring extension problem (prext) a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper coloring of the graph with the given number of colors. two parameterized versions of the problem are studied in the paper: either the number of precolored vertices or the number of colors used in the precoloring is restricted to be at most k. we show that for chordal graphs these problems are polynomial-time solvable for every fixed k, but w[1]-hard if k is the parameter. for a graph class f, let f + ke (resp., f + kv) denote those graphs that can be made to be a member of f by deleting at most k edges (resp., vertices). we investigate the connection between prext in f (with the two parameters defined above) and the coloring of f + ke, f + kv graphs (with k being the parameter). answering an open question of leizhen cai [parameterized complexity of vertex colouring, discrete appl. math. 127 (2003) 415-429], we show that coloring chordal+ke graphs is fixed-parameter tractable.
non-approximability of weighted multiple sequence alignment. we consider a weighted generalization of multiple sequence alignment (msa) with sum-of-pair score. msa without weights is known to be np-complete and can be approximated within a constant factor, but it is unknown whether it has a polynomial time approximation scheme. weighted multiple sequence alignment (wmsa) can be approximated within a factor of o(log2n) where n is the number of sequences.we prove that wmsa alignment is max jnp-hard and establish a numerical lower bound on its approximability, namely 324/323 - ε this lower bound is obtained already for the simple binary weighted case where the weights are restricted to 0 and 1. furthermore, we show that wmsa and its restriction to binary weights can be approximated to the same degree.
minimum sum multicoloring on the edges of trees. the edge multicoloring problem is that given a graph g and integer demands x (e) for every edge e, assign a set of x(e) colors to edge e, such that adjacent edges have disjoint sets of colors. in the minimum sum edge multicoloring problem the finish time of an edge is defined to be the highest color assigned to it. the goal is to minimize the sum of the finish times. the main result of the paper is a polynomial-time approximation scheme for minimum sum multicoloring the edges of trees. we also show that the problem is strongly np-hard for trees, even if every demand is at most 2.
the intractability of computing the hamming distance. given a string x and a language l, the hamming distance of x to l is the minimum hamming distance of x to any string in l. the edit distance of a string to a language is analogously defined.first, we prove that there is a language in ac0 such that both hamming and edit distance to this language are hard to approximate; they cannot be approximated with factor o(n(1/3)-ε), for any ε > 0, unless p = np (n denotes the length of the input string).second, we show the parameterized intractability of computing the hamming distance. we prove that for every t ∈ n there exists a language in ac0 for which computing the hamming distance is w[t]-hard. moreover, there is a language in p for which computing the hamming distance is wp-hard.then we show that the problems of computing the hamming distance and of computing the edit distance are in some sense equivalent by presenting approximation ratio preserving reductions from the former to the latter and vice versa.finally, we define hamp to be the class of languages to which the hamming distance can efficiently, i.e. in polynomial time, be computed. we show some properties of the class hamp. on the other hand, we give evidence that a characterization in terms of automata or formal languages might be difficult.
on computing the coefficients of bivariate holonomic formal series. in this work, we study the problem of computing the coefficients of holonomic formal series in two commuting variables. given a formal series φ(x, y) = σn,k ≥ 0 cnkxnyk specified by a holonomic system σj=0d1 pj(x, y)∂xjφ = 0 and σj=0d2qj(x, y)∂yjφ = 0 with a suitable finite set of intial conditions {[xayb]φ(x, y)}, we show that the coefficient [xiyj]φ(x, y) can be computed in time o(i + j) under the uniform cost criterion.
a new framework for addressing temporal range queries and some preliminary results. given a set of n objects, each characterized by d attributes specified at m fixed time instances, we are interested in the problem of designing space efficient indexing structures such that a class of temporal range search queries can be handled efficiently. when m = 1, our problem reduces to the d-dimensional orthogonal search problem. we establish efficient data structures to handle several classes of the general problem. our results include a linear size data structure that enables a query time of o(log n log m + f) for one-sided queries when d = 1, where f is the number of objects satisfying the query. a similar result is shown for counting queries. we also show that the most general problem can be solved with a polylogarithmic query time using superlinear space data structures.
quantum and classical tradeoffs. we initiate the study of quantifying the quantumness of a quantum circuit by the number of gates that do not preserve the computational basis, as a means to understand the nature of quantum algorithmic speedups. intuitively, a reduction in the quantumness requires an increase in the amount of classical computation, thus giving a "quantum and classical tradeoff'.in this paper we present two results on this measure of quantumness. the first gives almost matching upper and lower bounds on the question: "what is the minimum number of non-basis-preserving gates required to generate a good approximation to a given state". this question is the quantum analogy of the following classical question, "how many fair coins are needed to generate a given probability distribution", which was studied and resolved by knuth and yao in 1976 [algorithms and complexity: new directions and recent results, academic press, new york, 1976, pp. 357-428]. our second result shows that any quantum algorithm that solves grover's problem of size n using k queries and l levels of non-basis-preserving gates must have kl = ω(n).
asynchronous deterministic rendezvous in graphs. two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. we consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. the measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. if agents are initially situated at a distance d in an infinite line, we show a rendezvous algorithm with cost o(d|lmin|2) when d is known and o((d + |lmax|)3) if d is unknown, where |lmin| and |lmax| are the lengths of the shorter and longer label of the agents, respectively. these results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost o(n|lmin|), if the size n of the ring is known, and of cost o(n|lmax|), if it is unknown. for arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost o(d|lmin|) if the topology of the graph and the initial positions are known to agents.
design of abstract domains using first-order logic. in this paper we propose a simple framework based on first-order logic, for the design and decomposition of abstract domains for static analysis. an assertion language is chosen that specifies the properties of interest, and abstract domains are defined to be suitably chosen sets of assertions. composition and decomposition of abstract domains is facilitated by their logical specification in first-order logic. in particular, the operations of reduced product and disjunctive completion are formalized in this framework. moreover, the notion of (conjunctive) factorization of sets of assertions is introduced, that allows one to decompose domains in `disjoint'' parts. we illustrate the use of this framework by studying typical abstract domains for ground-dependency and aliasing analysis in logic programming.