Episciences.org
Not a member yet
6707 research outputs found
Sort by
Perfect Copositive Matrices
No full textIn this paper we give a first study of perfect copositive matrices. They can be used to find rational certificates for completelypositive matrices. We describe similarities and differences to classicalperfect, positive definite matrices. Most of the differences occur only for , where we find for instance lower rank and indefinite perfect matrices.Nevertheless, we find for all that for every classical perfect matrix thereis an arithmetically equivalent one which is also perfect copositive.Furthermore we study the neighborhood graph and polyhedral structure of perfectcopositive matrices. As an application we obtain a new characterization of thecone of completely positive matrices: It is equal to the set of nonnegativematrices having a nonnegative inner product with all perfect copositivematrices.Comment: 20 pages, 1 figur
Separating Sessions Smoothly
No full textThis paper introduces Hypersequent GV (HGV), a modular and extensible corecalculus for functional programming with session types that enjoys deadlockfreedom, confluence, and strong normalisation. HGV exploits hyper-environments,which are collections of type environments, to ensure that structuralcongruence is type preserving. As a consequence we obtain an operationalcorrespondence between HGV and HCP -- a process calculus based on hypersequentsand in a propositions-as-types correspondence with classical linear logic(CLL). Our translations from HGV to HCP and vice-versa both preserve andreflect reduction. HGV scales smoothly to support Girard's Mix rule, a crucialingredient for channel forwarding and exceptions
Network Capacity Bound for Personalized PageRank in Multimodal Networks
No full textIn a former paper the concept of Bipartite PageRank was introduced and atheorem on the limit of authority flowing between nodes for personalizedPageRank has been generalized. In this paper we want to extend those results tomultimodal networks. In particular we deal with a hypergraph type that may beused for describing multimodal network where a hyperlink connects nodes fromeach of the modalities. We introduce a generalisation of PageRank for suchgraphs and define the respective random walk model that can be used forcomputations. We state and prove theorems on the limit of outflow of authorityfor cases where individual modalities have identical and distinct dampingfactors.Comment: 21 pages. 2 tables, 30 bibliography position
Integrable Ito equations and properties of the associated Fokker-Planck equations
No full textIn a recent paper we have classified scalar Ito equations which admits astandard symmetry; these are also directly integrable by the Kozlovsubstitution. In the present work, we consider the diffusion (Fokker-Planck)equations associated to such symmetric Ito equations.Comment: 24 pages, no figure
Some statistics about Tropical Sandpile Model
No full textTropical sandpile model (or linearized sandpile model) is the only knowncontinuous geometric model exhibiting self-organised criticality. This modelrepresents the scaling limit behavior of a small perturbation of the maximalstable sandpile state on a big subset of . Given a set ofpoints in a compact convex domain this linearizedmodel produces a tropical polynomial . Here we present some quantitative statistical characteristics of this modeland some speculative explanations. Namely, we study the dependence between thenumber of randomly dropped points and the degree of the tropicalpolynomial . We also study the distributions of thecoefficients of and the correlation between them. Thispaper's main (experimental) result is that the tropical curve defined by is a small perturbation of thestandard square grid lines. This explains a previously known fact that most ofthe edges of the tropical curve are of directions. The main theoretical result is that , i.e. the tropical curve in with marked points removed, is a tree
Fixpoint Theory -- Upside Down
No full textKnaster-Tarski's theorem, characterising the greatest fixpoint of a monotonefunction over a complete lattice as the largest post-fixpoint, naturally leadsto the so-called coinduction proof principle for showing that some element isbelow the greatest fixpoint (e.g., for providing bisimilarity witnesses). Thedual principle, used for showing that an element is above the least fixpoint,is related to inductive invariants. In this paper we provide proof rules whichare similar in spirit but for showing that an element is above the greatestfixpoint or, dually, below the least fixpoint. The theory is developed fornon-expansive monotone functions on suitable lattices of the form, where is a finite set and an MV-algebra, andit is based on the construction of (finitary) approximations of the originalfunctions. We show that our theory applies to a wide range of examples,including termination probabilities, metric transition systems, behaviouraldistances for probabilistic automata and bisimilarity. Moreover it allows us todetermine original algorithms for solving simple stochastic games
Towards a Better Understanding of Tarajem: Creating Topological Networks for Arabic biographical Dictionaries
No full textBiographical writing is one of the earliest and most extensive forms of Arabic literature. Some scholars tend to assume that classical Arabic biographies, widely known as Tarāǧim, arose in conjunction with the study of the reliability of the Hadith transmitters (the reciters of the Prophet Mohammad's sayings) which lead to a proliferation of biographical material collected and used to assess the transmitter's trustworthiness . However, a scrutiny of the well-known classical Arabic biographical dictionaries such as Siyaru 'A`lāmi an-Nubalā' `The Lives of the Noble Figures' for Adh-Dhahabī shows that they extend their entries to other classes of persons important to the development of particular fields such as Islamic jurisprudents, rulers, poets, philosophers or physicians. The main contribution of Arabic biographical dictionaries is the cumulative value of the thousands of life histories which construct a picture of the Islamic society in different eras. An Arabic biographical dictionary, therefore, is predominantly used by scholars to look up an eminent person's achievements and historical background. In this project, however, we explore Arabic biographies as a prosopography, rather than a biography in the strict sense. We introduce a novel method for a better understanding of Arabic biographical dictionaries by creating a network of relations among different persons. We utilise Natural Language Processing (NLP) tools to create a topological network from the unstructured data of 45,500 biographical entries collected from different dictionaries. We aim to illustrate how network analysis leveraged by NLP tools can provide scholars with innovative methods for discovering complex constellation of relations between prominent and non-prominent figures spanning over several eras and from different fields of knowledge. We also use graph visualisation as a means to effectively communicate and explore such complex constellations. Each network visualisation is purposefully designed to be as simple and robust as possible to offer scholars a way to move relatively fluidly between the large scale of biographical entries and to easily interpret the minute ties between persons of different walks of life. We make both our data and code publicly available for researchers to replicate the experiment. It can be found at:https://github.com/sadanyh/Relational-Network-for-Arabic-Taraje
On the number of lattice points in a ball
No full textWe prove a fairly general inequality that estimates the number of latticepoints in a ball of positive radius in general position in a Euclidean space.The bound is uniform over lattices induced by a matrix having a boundedoperator norm
Proximal gradient methods beyond monotony
No full textWe address composite optimization problems, which consist in minimizing thesum of a smooth and a merely lower semicontinuous function, without anyconvexity assumptions. Numerical solutions of these problems can be obtained byproximal gradient methods, which often rely on a line search procedure asglobalization mechanism. We consider an adaptive nonmonotone proximal gradientscheme based on an averaged merit function and establish asymptotic convergenceguarantees under weak assumptions, delivering results on par with the monotonestrategy. Global worst-case rates for the iterates and a stationarity measureare also derived. Finally, a numerical example indicates the potential ofnonmonotonicity and spectral approximations.Comment: 18 pages, 1 algorithm, 1 figur
Gallai's Path Decomposition for 2-degenerate Graphs
No full textGallai's path decomposition conjecture states that if is a connectedgraph on vertices, then the edges of can be decomposed into at most paths. A graph is said to be an odd semi-clique ifit can be obtained from a clique on vertices by deleting at most edges. Bonamy and Perrett asked if the edges of every connected graph on vertices can be decomposed into at most pathsunless is an odd semi-clique. A graph is said to be 2-degenerate ifevery subgraph of has a vertex of degree at most . In this paper, weprove that the edges of any connected 2-degenerate graph on verticescan be decomposed into at most paths unless is a triangle.Comment: 11 pages, 5 figure