Episciences.org
Not a member yet
6707 research outputs found
Sort by
A localized Erdős-Kac theorem for
No full textLet denote the number of distinct prime divisors of less than . Suppose is an increasing sequence of positive real numbers satisfying . In this paper, we prove an Erd\"{o}s-Kac theorem for the distribution of , where runs over all prime numbers and is a fixed integer. We also highlight the connection between the distribution of and Ihara's conjectures on Euler-Kronecker constants
Concurrent Process Histories and Resource Transducers
No full textWe identify the algebraic structure of the material histories generated byconcurrent processes. Specifically, we extend existing categorical theories ofresource convertibility to capture concurrent interaction. Our formalism admitsan intuitive graphical presentation via string diagrams for proarrowequipments. We also consider certain induced categories of resourcetransducers, which are of independent interest due to their unusual structure
Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker
No full textThreshold guards are a basic primitive of many fault-tolerant algorithms thatsolve classical problems in distributed computing, such as reliable broadcast,two-phase commit, and consensus. Moreover, threshold guards can be found inrecent blockchain algorithms such as, e.g., Tendermint consensus. In thisarticle, we give an overview of techniques for automated verification ofthreshold-guarded fault-tolerant distributed algorithms, implemented in theByzantine Model Checker (ByMC). These threshold-guarded algorithms have thefollowing features: (1) up to of processes may crash or behave Byzantine;(2) the correct processes count messages and make progress when they receivesufficiently many messages, e.g., at least ; (3) the number ofprocesses in the system is a parameter, as well as the number of faults;and (4) the parameters are restricted by a resilience condition, e.g., . Traditionally, these algorithms were implemented in distributed systemswith up to ten participating processes. Nowadays, they are implemented indistributed systems that involve hundreds or thousands of processes. To makesure that these algorithms are still correct for that scale, it is imperativeto verify them for all possible values of the parameters
Fully Dynamic Connectivity in Amortized Expected Time
No full textDynamic connectivity is one of the most fundamental problems in dynamic graphalgorithms. We present a randomized Las Vegas dynamic connectivity datastructure with amortized expected update time and worst case query time, which comes very close to thecell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup(2011)
Certain Paracontact Metrics Satisfying the Critical Point Equation
No full textThe aim of this paper is to study theCPE (Critical Point Equation) on some paracontact metric manifolds.First, we prove that if a para-Sasakian metric satisfies the CPE,then it is Einstein with constant scalar curvature -2n(2n+1). Next,we prove that if -paracontact metric satisfies theCPE, then it is locally isometric to the product of a flat-dimensional manifold and -dimensional manifold ofnegative constant curvature
Congruences concerning Legendre polynomials modulo p^2
No full textIn this article, we extend Z. H. Sun's congruences concerning Legendre polynomials P p−1 2 (x) to P p+1 2 (x) for odd prime p, which enables us to deduce some congruences resembling p+1 2 ∑ k=0 4pk + 4k 2 − 1 16 k (2k − 1) 2 (2k k)2 (mod p 2)
Partial frames, their free frames and their congruence frames
No full textThe context of this work is that of partial frames; these aremeet-semilattices where not all subsets need have joins. A selection function,S, specifies, for all meet-semilattices, certain subsets under consideration,which we call the ``designated'' ones; an S-frame then must have joins of (atleast) all such subsets and binary meet must distribute over these. A smallcollection of axioms suffices to specify our selection functions; these axiomsare sufficiently general to include as examples of partial frames, boundeddistributive lattices, sigma-frames, kappa-frames and frames. We consider rightand left adjoints of S-frame maps, as a prelude to the introduction of closedand open maps. Then we look at what might be an appropriate notion of Booleanness forpartial frames. The obvious candidate is the condition that every element becomplemented; this concept is indeed of interest, but we pose three furtherconditions which, in the frame setting, are all equivalent to it. However, inthe context of partial frames, the four conditions are distinct. Ininvestigating these, we make essential use of the free frame over a partialframe and the congruence frame of a partial frame. We compare congruences of a partial frame, technically called S-congruences,with the frame congruences of its free frame. We provide a naturaltransformation for the situation and also consider right adjoints of the framemaps in question. We characterize the case where the two congruence frames areisomorphic and provide examples which illuminate the possible differentbehaviour of the two. We conclude with a characterization of closedness andopenness for the embedding of a partial frame into its free fame, and into itscongruence frame
Neural Coding as a Statistical Testing Problem
No full textWe take the testing perspective to understand what the minimal discriminationtime between two stimuli is for different types of rate coding neurons. Ourmain goal is to describe the testing abilities of two different encodingsystems: place cells and grid cells. In particular, we show, through the notionof adaptation, that a fixed place cell system can have a minimum discriminationtime that decreases when the stimuli are further away. This could be aconsiderable advantage for the place cell system that could complement the gridcell system, which is able to discriminate stimuli that are much closer thanplace cells
Robustness against Read Committed for Transaction Templates with Functional Constraints
No full textThe popular isolation level Multiversion Read Committed (RC) trades some ofthe strong guarantees of serializability for increased transaction throughput.Sometimes, transaction workloads can be safely executed under RC obtainingserializability at the lower cost of RC. Such workloads are said to be robustagainst RC. Previous work has yielded a tractable procedure for decidingrobustness against RC for workloads generated by transaction programs modeledas transaction templates. An important insight of that work is that, by moreaccurately modeling transaction programs, we are able to recognize larger setsof workloads as robust. In this work, we increase the modeling power oftransaction templates by extending them with functional constraints, which areuseful for capturing data dependencies like foreign keys. We show that theincorporation of functional constraints can identify more workloads as robustthat otherwise would not be. Even though we establish that the robustnessproblem becomes undecidable in its most general form, we show that variousrestrictions on functional constraints lead to decidable and even tractablefragments that can be used to model and test for robustness against RC forrealistic scenarios