Episciences.org
Not a member yet
6707 research outputs found
Sort by
On algebraically coisotropic submanifolds of holomorphic symplectic manifolds
No full textWe investigate algebraically coisotropic submanifolds in a holomorphicsymplectic projective manifold . Motivated by our results in thehypersurface case, we raise the following question: when is not uniruled,is it true that up to a finite \'etale cover, the pair is a product where are holomorphic symplectic and Z\subsetN is Lagrangian? We prove that this is indeed the case when is an abelianvariety, and give some partial answer when the canonical bundle issemi-ample. In particular, when is nef and big, is Lagrangian in (in fact this also holds without nefness assumption). We also remark thatLagrangian submanifolds do not exist on a sufficiently general Abelian variety,in contrast to the case when is irreducible hyperk\"ahler.Comment: 17 pages. v2: an improvement following a recent work of B. Taji (results valid for fibers with good minimal models rather than semiample canonical bundle). V3: minor corrections, a remark adde
Categorical composable cryptography: extended version
No full textWe formalize the simulation paradigm of cryptography in terms of categorytheory and show that protocols secure against abstract attacks form a symmetricmonoidal category, thus giving an abstract model of composable securitydefinitions in cryptography. Our model is able to incorporate computationalsecurity, set-up assumptions and various attack models such as colluding orindependently acting subsets of adversaries in a modular, flexible fashion. Weconclude by using string diagrams to rederive the security of the one-time pad,correctness of Diffie-Hellman key exchange and no-go results concerning thelimits of bipartite and tripartite cryptography, ruling out e.g., composablecommitments and broadcasting. On the way, we exhibit two categoricalconstructions of resource theories that might be of independent interest: onecapturing resources shared among multiple parties and one capturing resourceconversions that succeed asymptotically.Comment: Extended version of arXiv:2105.05949 which appeared in FoSSaCS 202
Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version)
No full textSemi-unification is the combination of first-order unification andfirst-order matching. The undecidability of semi-unification has been proven byKfoury, Tiuryn, and Urzyczyn in the 1990s by Turing reduction from Turingmachine immortality (existence of a diverging configuration). The particularTuring reduction is intricate, uses non-computational principles, and involvesvarious intermediate models of computation. The present work gives aconstructive many-one reduction from the Turing machine halting problem tosemi-unification. This establishes RE-completeness of semi-unification undermany-one reductions. Computability of the reduction function, constructivity ofthe argument, and correctness of the argument is witnessed by an axiom-freemechanization in the Coq proof assistant. Arguably, this serves ascomprehensive, precise, and surveyable evidence for the result at hand. Themechanization is incorporated into the existing, well-maintained Coq library ofundecidability proofs. Notably, a variant of Hooper's argument for theundecidability of Turing machine immortality is part of the mechanization
A Trichotomy for Regular Trail Queries
No full textRegular path queries (RPQs) are an essential component of graph querylanguages. Such queries consider a regular expression r and a directededge-labeled graph G and search for paths in G for which the sequence of labelsis in the language of r. In order to avoid having to consider infinitely manypaths, some database engines restrict such paths to be trails, that is, theyonly consider paths without repeated edges. In this paper we consider theevaluation problem for RPQs under trail semantics, in the case where theexpression is fixed. We show that, in this setting, there exists a trichotomy.More precisely, the complexity of RPQ evaluation divides the regular languagesinto the finite languages, the class Ttract (for which the problem istractable), and the rest. Interestingly, the tractable class in the trichotomyis larger than for the trichotomy for simple paths, discovered by Bagan,Bonifati, and Groz [JCSS 2020]. In addition to this trichotomy result, we alsostudy characterizations of the tractable class, its expressivity, therecognition problem, closure properties, and show how the decision problem canbe extended to the enumeration problem, which is relevant to practice
The Challenges of HTR Model Training: Feedback from the Project Donner le gout de l'archive a l'ere numerique
No full textThe arrival of handwriting recognition technologies offers new possibilitiesfor research in heritage studies. However, it is now necessary to reflect onthe experiences and the practices developed by research teams. Our use of theTranskribus platform since 2018 has led us to search for the most significantways to improve the performance of our handwritten text recognition (HTR)models which are made to transcribe French handwriting dating from the 17thcentury. This article therefore reports on the impacts of creating transcribingprotocols, using the language model at full scale and determining the best wayto use base models in order to help increase the performance of HTR models.Combining all of these elements can indeed increase the performance of a singlemodel by more than 20% (reaching a Character Error Rate below 5%). This articlealso discusses some challenges regarding the collaborative nature of HTRplatforms such as Transkribus and the way researchers can share their datagenerated in the process of creating or training handwritten text recognitionmodels
Monotones in General Resource Theories
No full textA central problem in the study of resource theories is to find functions thatare nonincreasing under resource conversions - termed monotones - in order toquantify resourcefulness. Various constructions of monotones appear in manydifferent concrete resource theories. How general are these constructions? Whatare the necessary conditions on a resource theory for a given construction tobe applicable? To answer these questions, we introduce a broad scheme forconstructing monotones. It involves finding an order-preserving map from thepreorder of resources of interest to a distinct preorder for which nontrivialmonotones are previously known or can be more easily constructed; thesemonotones are then pulled back through the map. In one of the two main classeswe study, the preorder of resources is mapped to a preorder of sets ofresources, where the order relation is set inclusion, such that monotones canbe defined via maximizing or minimizing the value of a function within thesesets. In the other class, the preorder of resources is mapped to a preorder oftuples of resources, and one pulls back monotones that measure the amount ofdistinguishability of the different elements of the tuple (hence itsinformation content). Monotones based on contractions arise naturally in thelatter class, and, more surprisingly, so do weight and robustness measures. Inaddition to capturing many standard monotone constructions, our scheme alsosuggests significant generalizations of these. In order to properly capture thebreadth of applicability of our results, we present them within a novelabstract framework for resource theories in which the notion of composition isindependent of the types of the resources involved (i.e., whether they arestates, channels, combs, etc.).Comment: 47 pages, 4 figures. v3: Updated content thanks to anonymous reviewers. We added background material on resource theories via Ex. 8 & 9, as well as a table providing an overview of our monotone constructions in Appendix
Koszul duality for operadic categories
No full textThe aim of this sequel to arXiv:1812.02935 is to set up the cornerstones ofKoszul duality and Koszulity in the context of operads over a large class ofoperadic categories. In particular, for these operadic categories we will studyconcrete examples of binary quadratic operads, describe their Koszul duals andprove that they are Koszul. This includes operads whose algebras are the mostimportant operad- and PROP-like structures such as the classical operads, theirvariants such as cyclic, modular or wheeled operads, and also diverse versionsof PROPs such as properads, dioperads, 1/2PROPs, and still more exotic objectssuch as permutads and pre-permutads.Comment: 56 pages. Final version. arXiv admin note: substantial text overlap with arXiv:1812.0293
Le dialogue interdisciplinaire clarifie l'enseignement disciplinaire
No full textSince 2019, at the Institut de Recherche sur l'Enseignement des Sciences in Aix-Marseille Université, we have been running a workshop aimed at exploring solutions to the difficulties regularly encountered in interdisciplinary teaching. At regular intervals, this workshop brings together six teachers from different disciplines - from university and high school - who are simply given the time to present and explain to each other the specificities of the discipline they teach, using a basic categorial grid to guide analysis and enable comparison. However, our initial findings indicate that the primary beneficiary of these interdisciplinary encounters is disciplinary teaching itself. In fact, this introspective and collective work has brought to light fundamental implicits, specific or common, to these disciplines that teachers were unaware of; that they had never shared with their students; and that they identified as the source of hitherto unspeakable difficulties encountered by many of them. The hypothesis defended here is therefore that - through an effect of analogies and contrasts - interdisciplinary dialogue can be a formidable tool for reinforcing and clarifying disciplinary teaching, and could play a key role in teacher training.Depuis 2019, au sein de l’Institut de Recherche sur l’Enseignement des Sciences d’Aix-Marseille Université, nous animons un atelier visant à explorer des solutions aux difficultés régulièrement rencontrées dans l’enseignement interdisciplinaire. Cet atelier réunit à intervalles réguliers six enseignants de disciplines différentes — de l’université et du lycée — auxquels est simplement donné le temps de présenter et expliquer les uns aux autres les spécificités de la discipline qu’ils enseignent, à l’aide d’une grille catégorielle élémentaire, guidant l’analyse et permettant la comparaison. Or, nos premières conclusions indiquent que le premier bénéficiaire de ces rencontres interdisciplinaires est l’enseignement disciplinaire lui-même. De fait, ce travail introspectif et collectif a fait émerger des implicites fondamentaux spécifiques ou communs à ces disciplines dont les enseignants n’avaient pas conscience ; qu’ils n’avaient jamais partagé avec leurs élèves ; et qu’ils ont identifié comme la source de difficultés jusque-là inexprimables rencontrées par nombre d’entre eux. L’hypothèse défendue ici est donc que — par effet d’analogies et de contrastes — le dialogue interdisciplinaire peut être un formidable outil de renforcement et de clarification de l’enseignement disciplinaire, qui pourrait jouer un rôle clé dans la formation des enseignants
A coherent differential PCF
No full textThe categorical models of the differential lambda-calculus are additivecategories because of the Leibniz rule which requires the summation of twoexpressions. This means that, as far as the differential lambda-calculus anddifferential linear logic are concerned, these models feature finitenon-determinism and indeed these languages are essentially non-deterministic.In a previous paper we introduced a categorical framework for differentiationwhich does not require additivity and is compatible with deterministic modelssuch as coherence spaces and probabilistic models such as probabilisticcoherence spaces. Based on this semantics we develop a syntax of adeterministic version of the differential lambda-calculus. One nice feature ofthis new approach to differentiation is that it is compatible with generalfixpoints of terms, so our language is actually a differential extension of PCFfor which we provide a fully deterministic operational semantics
Methods for Efficient Unfolding of Colored Petri Nets
No full textColored Petri nets offer a compact and user friendly representation of thetraditional P/T nets and colored nets with finite color ranges can be unfoldedinto the underlying P/T nets, however, at the expense of an exponentialexplosion in size. We present two novel techniques based on static analysis inorder to reduce the size of unfolded colored nets. The first method identifiescolors that behave equivalently and groups them into equivalence classes,potentially reducing the number of used colors. The second methodoverapproximates the sets of colors that can appear in places and excludescolors that can never be present in a given place. Both methods arecomplementary and the combined approach allows us to significantly reduce thesize of multiple colored Petri nets from the Model Checking Contest benchmark.We compare the performance of our unfolder with state-of-the-art techniquesimplemented in the tools MCC, Spike and ITS-Tools, and while our approach iscompetitive w.r.t. unfolding time, it also outperforms the existing approachesboth in the size of unfolded nets as well as in the number of answered modelchecking queries from the 2021 Model Checking Contest