Episciences.org
Not a member yet
6707 research outputs found
Sort by
Fine-Grained Complexity of Regular Path Queries
No full textA regular path query (RPQ) is a regular expression q that returns all nodepairs (u, v) from a graph database that are connected by an arbitrary pathlabelled with a word from L(q). The obvious algorithmic approach toRPQ-evaluation (called PG-approach), i.e., constructing the product graphbetween an NFA for q and the graph database, is appealing due to its simplicityand also leads to efficient algorithms. However, it is unclear whether thePG-approach is optimal. We address this question by thoroughly investigatingwhich upper complexity bounds can be achieved by the PG-approach, and wecomplement these with conditional lower bounds (in the sense of thefine-grained complexity framework). A special focus is put on enumeration anddelay bounds, as well as the data complexity perspective. A main insight isthat we can achieve optimal (or near optimal) algorithms with the PG-approach,but the delay for enumeration is rather high (linear in the database). Weexplore three successful approaches towards enumeration with sub-linear delay:super-linear preprocessing, approximations of the solution sets, and restrictedclasses of RPQs
Measures of association between algebraic varieties, II: self-correspondences
No full textFollowing a suggestion of Jordan Ellenberg, we study measures of complexityfor self-correspondences of some classes of varieties. We also answer aquestion of Rhyd concerning curves sitting in the square of a very generalhyperelliptic curve.Comment: This article is dedicated to Claire Voisin on the occasion of her birthday. 12 page
Lire et interpréter la philosophie économique d'Ibn Khaldun
No full textDiese Arbeit zielt darauf ab, Schlüsselkonzepte, Ideen und Ereignisse darzustellen, die sich hauptsächlich aus Ibn Khalduns Kapitel über das Wirtschaftsleben ableiten lassen, das er mit der Überschrift „Kapitel über den Lebensunterhalt“ (ma`āsh) zusammenfasst. Die Rechtfertigung dieses Unterfangens ist die Bedeutung von Ibn Khalduns Beiträgen, der Mangel an Übersetzungen seiner Werke und die Abhängigkeit sekundärer Interpretationswerke von einer einzigen englischen Übersetzung. Während die Lektüre der Wirtschaftsphilosophie von Ibn Khaldun durch eine Textanalyse der Primärquellen weiterhin im Mittelpunkt dieser Arbeit steht, wird hier auch eine Auswahl der Interpretations- und Übersetzungswerke präsentiert, um den Grad der Auseinandersetzung nichtarabischer Gelehrter mit Ibn zu verstehen Khalduns Werk und als Geisteshaltung, mit der sich Wirtschaftsphilosophen und Sozialhistoriker auseinandersetzen könnten.This work aims to present key concepts, ideas, and events that can be derived mainly from Ibn Khaldun’s chapter on economic life, which he captures with the heading, Chapter on Making a Living (ma`āsh). Justifying this undertaking is the significance of Ibn Khaldun’s contributions, the scarcity of translations of his work, and the dependency of secondary interpretive works on a single English translation. While a reading of Ibn Khaldun’s economic philosophy through a textual analysis of the primary sources remains the focus of this work, a sampling of the interpretive and translation works is also presented here in order to understand the level of engagement of non-Arabic scholars with Ibn Khaldun’s work and as a frame of mind with which economic philosophers and social historians might engage.Cet ouvrage vise à présenter des concepts, des idées et des événements clés qui peuvent être dérivés principalement du chapitre d’Ibn Khaldun sur la vie économique, qu’il capture sous le titre Chapitre sur Gagner sa vie (ma`āsh). Cette entreprise est justifiée par l’importance des contributions d’Ibn Khaldun, la rareté des traductions de son œuvre et la dépendance des travaux d’interprétation secondaires à une seule traduction anglaise. Bien qu'une lecture de la philosophie économique d'Ibn Khaldun à travers une analyse textuelle des sources primaires reste au centre de ce travail, un échantillon des travaux d'interprétation et de traduction est également présenté ici afin de comprendre le niveau d'engagement des érudits non arabes avec Ibn Khaldun. Khaldun et comme état d'esprit dans lequel les philosophes économiques et les historiens sociaux pourraient s'engager
Pseudoperiodic Words and a Question of Shevelev
No full textWe generalize the familiar notion of periodicity in sequences to a new kindof pseudoperiodicity, and we prove some basic results about it. We revisit theresults of a 2012 paper of Shevelev and reprove his results in a simpler andmore unified manner, and provide a complete answer to one of his previouslyunresolved questions. We consider finding words with specific pseudoperiod andhaving the smallest possible critical exponent. Finally, we consider theproblem of determining whether a finite word is pseudoperiodic of a given size,and show that it is NP-complete
On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
No full textSynthesis consists in deciding whether a given labeled transition system (TS) can be implemented by a net of type . In case of a negativedecision, it may be possible to convert into an implementable TS byapplying various modification techniques, like relabeling edges that previouslyhad the same label, suppressing edges/states/events, etc. It may however beuseful to limit the number of such modifications to stay close to the originalproblem, or optimize the technique. In this paper, we show that most of thecorresponding problems are NP-complete if corresponds to the type offlip-flop nets or some flip-flop net derivatives
String Covering: A Survey
No full textThe study of strings is an important combinatorial field that precedes thedigital computer. Strings can be very long, trillions of letters, so it isimportant to find compact representations. Here we first survey various formsof one potential compaction methodology, the cover of a given string x,initially proposed in a simple form in 1990, but increasingly of interest asmore sophisticated variants have been discovered. We then consider covering bya seed; that is, a cover of a superstring of x. We conclude with many proposalsfor research directions that could make significant contributions to stringprocessing in future
Diameter of General Kn\"odel Graphs
No full textThe Kn\"odel graph is a -regular bipartition graph on vertices and is an even integer. The vertices of are the pairs with and . Forevery , , there is an edge between vertex andevery vertex , for . In thispaper we obtain some formulas for evaluating the distance of vertices of theKn\"odel graph and by them, we provide the formula for the diameter of, where .Comment: 16 pages, 1 table, 2 figure
Relaxation in one-dimensional tropical sandpile
No full textA relaxation in the tropical sandpile model is a process of deforming atropical hypersurface towards a finite collection of points. We show that, inthe one-dimensional case, a relaxation terminates after a finite number ofsteps. We present experimental evidence suggesting that the number of suchsteps obeys a power law
Dynamic Separation Logic
No full textThis paper introduces a dynamic logic extension of separation logic. Theassertion language of separation logic is extended with modalities for the fivetypes of the basic instructions of separation logic: simple assignment,look-up, mutation, allocation, and de-allocation. The main novelty of theresulting dynamic logic is that it allows to combine different approaches toresolving these modalities. One such approach is based on the standard weakestprecondition calculus of separation logic. The other approach introduced inthis paper provides a novel alternative formalization in the proposed dynamiclogic extension of separation logic. The soundness and completeness of thisaxiomatization has been formalized in the Coq theorem prover
Propositional Logics for the Lawvere Quantale
No full textLawvere showed that generalised metric spaces are categories enriched over, the quantale of the positive extended reals. The statement ofenrichment is a quantitative analogue of being a preorder. Towards seeking alogic for quantitative metric reasoning, we investigate three-valued propositional logics over the Lawvere quantale. The basiclogical connectives shared by all three logics are those that can beinterpreted in any quantale, viz finite conjunctions and disjunctions, tensor(addition for the Lawvere quantale) and linear implication (here a truncatedsubtraction); to these we add, in turn, the constant to express integervalues, and scalar multiplication by a non-negative real to express generalaffine combinations. Quantitative equational logic can be interpreted in thethird logic if we allow inference systems instead of axiomatic systems. Foreach of these logics we develop a natural deduction system which we prove to bedecidably complete w.r.t. the quantale-valued semantics. The heart of thecompleteness proof makes use of the Motzkin transposition theorem. Consistencyis also decidable; the proof makes use of Fourier-Motzkin elimination of linearinequalities. Strong completeness does not hold in general, even (as is known)for theories over finitely-many propositional variables; indeed even anapproximate form of strong completeness in the sense of Pavelka or Ben Yaacov-- provability up to arbitrary precision -- does not hold. However, we can showit for theories axiomatized by a (not necessarily finite) set of judgements innormal form over a finite set of propositional variables when we restrict tomodels that do not map variables to ; the proof uses Hurwicz's generalform of the Farkas' Lemma