waashk/dblp huggingface dataset:
topological properties of real number representations. we prove three results about representations of real numbers (or elements of other topological spaces) by infinite strings. such representations are useful for the description of real number computations performed by digital computers or by turing machines. first, we show that the so-called admissible representations, a topologically natural class of representations introduced by kreitz and weihrauch, are essentially the continuous extensions (with a well-behaved domain) of continuous and open representations. second, we show that there is no admissible representation of the real numbers such that every real number has only finitely many names. third, we show that a rather interesting property of admissible real number representations holds true also for a certain non-admissible representation, namely for the naive cauchy representation: the property that continuity is equivalent to relative continuity with respect to the representation.
computability on subsets of metric spaces. the notions "recursively enumerable" and "recursive" are the basic notions of effectivity in classical recursion theory. in computable analysis, these notions are generalized to closed subsets of euclidean space using their metric distance functions. we study a further generalization of these concepts to subsets of computable metric spaces. it appears that different characterizations, which coincide in case of euclidean space, lead to different notions in the general case. however, under certain additional conditions, such as completeness and effective local compactness, the situation is similar to the euclidean case. we present all results in the framework of "type-2 theory of effectivity" which allows to express effectivity properties in a very uniform way: instead of comparing properties of single subsets, we compare corresponding representations of the hyperspace of closed subsets. such representations do not only induce a concept of computability for single subsets, but they even yield a concept of computability for operations on hyperspaces, such as union, intersection, etc. we complete our investigation by studying the special situation of compact subsets.
discrete time generative-reactive probabilistic processes with different advancing speeds. we present a process algebra expressing probabilistic external/internal choices, multi-way synchronizations, and processes with different advancing speeds in the context of discrete time, i.e. where time is not continuous but is represented by a sequence of discrete steps as in discrete time markov chains (dtmcs). to this end, we introduce a variant of csp that employs a probabilistic asynchronous parallel operator whose synchronization mechanism is based on a mixture of the classical generative and reactive models of probability. in particular, differently from existing discrete time process algebras, where parallel processes are executed in synchronous locksteps, the parallel operator that we adopt allows processes with different probabilistic advancing speeds (mean number of actions executed per time unit) to be modeled. moreover, our generative-reactive synchronization mechanism makes it possible to always derive dtmcs in the case of fully specified systems. we then present a sound and complete axiomatization of probabilistic bisimulation over finite processes of our calculus, that is a smooth extension of the axiom system for a standard process algebra, thus solving the open problem of cleanly axiomatizing action restriction in the generative model. as a further result, we show that, when evaluating steady state based performance measures which are expressible by attaching rewards to actions, our approach provides an exact solution even if the advancing speeds are considered not to be probabilistic, without incurring the state space explosion problem that arises with standard synchronous approaches. we finally present a case study on multi-path routing showing the expressiveness of our calculus and that it makes it particularly easy to produce scalable specifications.
the theory of interactive generalized semi-markov processes. in this paper we introduce the calculus of interactive generalized semi-markov processes (igsmps), a stochastic process algebra which can express probabilistic timed delays with general distributions and synchronizable actions with zero duration, and where choices may be probabilistic, non-deterministic and prioritized. igsmp is equipped with a structural operational semantics which generates semantic models in the form of generalized semi-markov processes (gsmps), i.e. probabilistic systems with generally distributed time, extended with action transitions representing interaction among system components. this is obtained by expressing the concurrent execution of delays through a variant of st semantics which is based on dynamic names. the fact that names for delays are generated dynamically by the semantics makes it possible to define a notion of observational congruence for igsmp (that abstracts from internal actions with zero duration) simply as a combination of standard observational congruence and probabilistic bisimulation. we also present a complete axiomatization for observational congruence over igsmp. finally, we show how to derive a gsmp from a given igsmp specification in order to evaluate the system performance and we present a case study.
quantitative information in the tuple space coordination model. tuple spaces is a well-known coordination model at the basis of coordination languages such as linda, javaspaces and tspaces. tuple spaces are flat and unstructured multisets of tuples that can be accessed via output, read, and input operations. we investigate, from an expressiveness viewpoint, the impact of the introduction of quantitative information in the tuple space coordination model in order to quantify the relevance or importance of each tuple. we consider two possible interpretations for this information: in the first case it quantifies a weight indicating how much frequently each tuple should be retrieved, in the second case it expresses a priority level for the tuples.
strand design for biomolecular computation. the design of dna or rna strands for dna computations poses many new questions in algorithms and coding theory. dna strand design also arises in use of molecular bar codes to manipulate and identify individual molecules in complex chemical libraries, and to attach molecules to dna chips. we survey several formulations of the dna strand design problem, along with results and open questions in this area.
compatible topologies on graphs: an application to graph isomorphism problem complexity. in one hand the graph isomorphism problem (gi) has received considerable attention due to its unresolved complexity status and is many practical applications. on the other hand a notion of compatible topologies on graphs has emerged from digital topology (see [a. bretto, comparability graphs and digital topology, comput. vision graphic image process. (image understanding), 82 (2001) 33-41; j.m. chassery, connectivity and consecutivity in digital pictures, comput. vision graphic image process. 9 (1979) 294-300; l.j. latecki, topological connectedness and 8-connectness in digital pictures, cvgip image understanding 57(2) (1993) 261-262; u. eckhardt, l.j. latecki, topologies for digital spaces z2 and z3, comput. vision image understanding 95 (2003) 261-262; t.y. kong, r. kopperman, p.r. meyer, a topological approach to digital topology, amer. math. monthly archive 98(12) (1991) 901-917; r. kopperman, topological digital topology, discrete geometry for computer imagery, 11th international conference, lecture notes in computer science, vol. 2886, dgci 2003, naples, italy, november 19-21, pp. 1-15]).in this article we study gi from the topological point of view. firstly, we explore the poset of compatible topologies on graphs and in particular on bipartite graphs. then, from a graph we construct a particular compatible alexandroff topological space said homeomorphic-equivalent to the graph. conversely, from any alexandroff topology we construct an isomorphic-equivalent graph on which the topology is compatible. finally, using these constructions, we show that gi is polynomial-time equivalent to the topological homeomorphism problem (tophomeo). hence gi and tophomeo are in the same class of complexity.
terminal metric spaces of finitely branching and image finite linear processes. well-known metric spaces for modelling finitely branching and image finite systems are shown to be (the carrier of) terminal coalgebras.
domain theory, testing and simulation for labelled markov processes. this paper presents a fundamental study of similarity and bisimilarity for labelled markov processes (lmps). the main results characterize similarity as a testing preorder and bisimilarity as a testing equivalence. in general, lmps are not required to satisfy a finite-branching condition--indeed the state space may be a continuum, with the transitions given by arbitrary probability measures. nevertheless we show that to characterize bisimilarity it suffices to use finitely-branching labelled trees as tests.our results involve an interaction between domain theory and measure theory. one of the main technical contributions is to show that a final object in a suitable category of lmps can be constructed by solving a domain equation d ≃v(d)act, where v is the probabilistic powerdomain. given an lmp whose state space is an analytic space, bisimilarity arises as the kernel of the unique map to the final lmp. we also show that the metric for approximate bisimilarity introduced by desharnais, gupta, jagadeesan and panangaden generates the lawson topology on the domain d.
a behavioural pseudometric for probabilistic transition systems. discrete notions of behavioural equivalence sit uneasily with semantic models featuring quantitative data, like probabilistic transition systems. in this paper, we present a pseudometric on a class of probabilistic transition systems yielding a quantitative notion of behavioural equivalence. the pseudometric is defined via the terminal coalgebra of a functor based on a metric on the space of borel probability measures on a metric space. states of a probabilistic transition system have distance 0 if and only if they are probabilistic bisimilar. we also characterize our distance function in terms of a real-valued modal logic.
approximating and computing behavioural distances in probabilistic transition systems. in an earlier paper we presented a pseudometric on the states of a probabilistic transition system, yielding a quantitative notion of behavioural equivalence. the behavioural pseudometric was defined via the terminal coalgebra of a functor based on a metric on borel probability measures. in the present paper we give a polynomial-time algorithm, based on linear programming, to calculate the distances between states up to a prescribed degree of accuracy.
making knowledge explicit: how hard it is. artemov's logic of proofs lp is a complete calculus of propositions and proofs, which is now becoming a foundation for the evidence-based approach to reasoning about knowledge. additional atoms in lp have form t: f, read as "t is a proof of f" (or, more generally, as "t is an evidence for f") for an appropriate system of terms t called proof polynomials. in this paper, we answer two well-known questions in this area. one of the main features of lp is its ability to realize modalities in any s4-derivation by proof polynomials thus revealing a statement about explicit evidences encoded in that derivation. we show that the original artemov's algorithm of building such realizations can produce proof polynomials of exponential length in the size of the initial s4-derivation. we modify the realization algorithm to produce proof polynomials of at most quadratic length. we also found a modal formula, any realization of which necessarily requires self-referential constants of type c: a(c). this demonstrates that the evidence-based reasoning encoded by the modal logic s4 is inherently self-referential.
kernels of seminorms in constructive analysis. the kernel of a seminorm on a normed space is examined constructively--that is, using intuitionistic logic. in particular, conditions are given that ensure that (i) the kernel is located and (ii) the kernel is nontrivial.
implementing exact real arithmetic in python, c++ and c. i discuss the design and performance issues arising in the efficient implementation of the scaled-integer exact real arithmetic model introduced by boehm and others. this system represents a real number with a automatically controlled level of precision by a rational with implicit denominator. i describe three practical codes, in python, c++ and c. these allow the convenient use of this computational paradigm in commonly used imperative languages.
reducibility of gene patterns in ciliates using the breakpoint graph. gene assembly in ciliates is one of the most involved dna processings going on in any organism. this process transforms one nucleus (the micronucleus) into another functionally different nucleus (the macronucleus). we continue the development of the theoretical models of gene assembly, and in particular we demonstrate the use of the concept of the breakpoint graph, known from another branch of dna transformation research. more specifically: (1) we characterize the intermediate gene patterns that can occur during the transformation of a given micronuclear gene pattern to its macronuclear form; (2) we determine the number of applications of the loop recombination operation (the most basic of the three molecular operations that accomplish gene assembly) needed in this transformation; (3) we generalize previous results (and give elegant alternatives for some proofs) concerning characterizations of the micronuclear gene patterns that can be assembled using a specific subset of the three molecular operations.
graceful planes and lines. in the framework of the theory of arithmetic geometry (reveills, gomtrie discrte, calcul en nombres entiers et algorithmique, thse d'tat, universit louis pasteur, strasbourg, 1991), we propose an approach to discretize polyhedra by meshes of discrete triangles. we propose a general discretization scheme based on reducing the 3d problem to a 2d problem. we introduce new classes of discrete planes and lines called graceful planes and graceful lines. naive planes and graceful lines are used to construct as thin as possible triangular mesh discretization admitting an analytical description. the interiors of the triangles are portions of naive planes, while the sides are graceful lines. these primitives serve as an optimal ground for obtaining thin tunnel-free discretizations, within the adopted generation scheme. we also extend our considerations to arbitrary surfaces and curves.
connectivity of discrete planes. studying connectivity of discrete objects is a major issue in discrete geometry and topology. in the present work, we deal with connectivity of discrete planes in the framework of réveillès analytical definition (thèse d'état, université louis pasteur, strasbourg, france, 1991). accordingly, a discrete plane is a set p(a, b, c, µ, ω) of integer points (x, y, z) satisfying the diophantine inequalities 0 ≤ ax + by + cz + µ < ω. the parameter µ ∈ z estimates the plane intercept while ω ∈ n is the plane thickness. given three integers (plane coefficients) a, b, and c with 0 ≤ a ≤ b ≤ c, one can seek the value of ω beyond which the discrete plane p(a, b, c, µ, ω) is always connected. we call this remarkable topological invariable the connectivity number of p(a, b, c, µ, ω) and denote it ω(a, b, c). despite several attempts over the last 10 years to determine the connectivity number, this is still an open question. in the present paper, we propose a solution to the problem. for this, we first investigate some combinatorial properties of discrete planes. these structural results facilitate the deeper understanding of the discrete plane structure. on this basis, we obtain a series of results, in particular, we provide an explicit solution to the problem under certain conditions. we also obtain exact upper and lower bounds on ω(a, b, c) and design an o(alogb) algorithm for its computation.
the modal argument for hypercomputing minds. we now know both that hypercomputation (or super-recursive computation) is mathematically well-understood, and that it provides a theory that according to some accounts for some real-life computation (e.g., operating systems that, unlike turing machines, never simply output an answer and halt) better than the standard theory of computation at and below the "turing limit." but one of the things we do not know is whether the human mind hypercomputes, or merely computes--this despite informal arguments from gödel, lucas, penrose and others for the view that, in light of incompleteness theorems, the human mind has powers exceeding those of tms and their equivalents. all these arguments fail; their fatal flaws have been repeatedly exposed in the literature. however, we give herein a novel, formal modal argument showing that since it's mathematically possible that human minds are hypercomputers, such minds are in fact hypercomputers. we take considerable pains to anticipate and rebut objections to this argument.
public data structures: counters as a special case. a public data structure is required to work correctly in a concurrent environment where many processes may try to access it, possibly at the same time. in implementing such a structure nothing can be assumed in advance about the number or the identities of the processes that might access it.while most of the known concurrent data structures are not public, there are few which are public. interestingly, these public data structures all deal with various variants of counters, which are data structures that support two operations: increment and read.in this paper, we define the notion of a public data structure, and investigate several types of public counters. then we give an optimal construction of public counters which satisfies a weak correcness condition, and show that there is no public counter which satisfies a stronger condition. it is hoped that this work will provide insights into the design of other, more complicated, public data structures.
combinatorial properties of smooth infinite words. we describe some combinatorial properties of an intriguing class of infinite words, called smooth, connected with the kolakoski one, k, defined as the fixed point of the run-length encoding δ. it is based on a bijection on the free monoid over σ = {1, 2}, that shows some surprising mixing properties. all words contain the same finite number of square factors, and consequently they are cube-free. this suggests that they have the same complexity as confirmed by extensive computations. we further investigate the occurrences of palindromic subwords. finally, we show that there exist smooth words obtained as fixed points of substitutions (realized by transducers) as in the case of k.
a note on differentiable palindromes. we give a characterization of the palindromes in a class of infinite words over σ = {1,2} related to the kolakoski word k. this characterization, based on the left palindromic closure of all prefixes of k, is obtained by using a bijection between the class of right infinite words over σ and a class of words over the same alphabet, and reveals the first link between the existence of some palindromes and the recurrence of k. indeed, the existence of arbitrarily long palindromes implies the recurrence of k, and a stronger assumption implies the closure of the set of its factors by permutation of the letters in σ.
the discrete green theorem and some applications in discrete geometry. the discrete version of green's theorem and bivariate difference calculus provide a general and unifying framework for the description and generation of incremental algorithms. it may be used to compute various statistics about regions bounded by a finite and closed polygonal path. more specifically, we illustrate its use for designing algorithms computing many statistics about polyominoes, regions whose boundary is encoded by four letter words: area, coordinates of the center of gravity, moment of inertia, set characteristic function, the intersection with a given set of pixels, hook-lengths, higher order moments and also q-statistics for projections.
on the power of non-local boxes. a non-local box is a virtual device that has the following property: given that alice inputs a bit at her end of the device and that bob does likewise, it produces two bits, one at alice's end and one at bob's end, such that the xor of the outputs is equal to the and of the inputs. this box, inspired from the chsh inequality, was first proposed by popescu and rohrlich to examine the question: given that a maximally entangled pair of qubits is non-local, why is it not maximally non-local? we believe that understanding the power of this box will yield insight into the non-locality of quantum mechanics. it was shown recently by cerf, gisin, massar and popescu, that this imaginary device is able to simulate correlations from any measurement on a singlet state. here, we show that the non-local box can in fact do much more: through the simulation of the magic square pseudo-telepathy game and the mermin-ghz pseudo-telepathy game, we show that the non-local box can simulate quantum correlations that no entangled pair of qubits can, in a bipartite scenario and even in a multi-party scenario. finally we show that a single non-local box cannot simulate all quantum correlations and propose a generalization for a multi-party non-local box. in particular, we show quantum correlations whose simulation requires an exponential amount of non-local boxes, in the number of maximally entangled qubit pairs.
the decidability of a fragment of bb'iw-logic. despite its simple formulation, the decidability of the logic <b>bb'iw</b> has remained an open problem. we present here a decision procedure for a fragment of it, called the arity-1 formulas. the decidability proof is based on a representation of formulas called formula-trees, which is coupled with a proof method that computes long normal λ-terms that inhabit a formula. a rewriting-system is associated with such λ-terms, and we show that a formula admits a <b>bb'iw</b>-λ-term if and only if the associated rewriting-system terminates. the fact that termination is decidable is proved using a result on the finiteness of non-ascending sequences of <i>n</i>-tuples in n<sup><i>n</i></sup>, which is equivalent to kripke's lemma.
space-efficient planar convex hull algorithms. a space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. we describe four space-efficient algorithms for computing the convex hull of a planar point set.
the design of the boost interval arithmetic library. we present the design of the boost interval arithmetic library, a c++ library designed to handle mathematical intervals efficiently and in a generic way. interval computations are an essential tool for reliable computing. increasingly a number of mathematical proofs have relied on global optimization problems solved using branch-and-bound algorithms with interval computations; it is therefore extremely important to have a mathematically correct implementation of interval arithmetic. various implementations exist with diverse semantics. our design is unique in that it uses policies to specify three independent variable behaviors: rounding, checking, and comparisons. as a result, with the proper policies, our interval library is able to emulate almost any of the specialized libraries available for interval arithmetic, without any loss of performance nor sacrificing the ease of use. this library is openly available at www.boost.org.