Episciences.org
Not a member yet
6707 research outputs found
Sort by
A new approach to integrals of discretizations by polarization
No full textRecently, a family of unconventional integrators for ODEs with polynomialvector fields was proposed, based on the polarization of vector fields. Thesimplest instance is the by now famous Kahan discretization for quadraticvector fields. All these integrators seem to possess remarkable conservationproperties. In particular, it has been proved that, when the underlying ODE isHamiltonian, its polarization discretization possesses an integral of motionand an invariant volume form. In this note, we propose a new algebraic approachto derivation of the integrals of motion for polarization discretizations.Comment: v2 re-formatted for the journa
«Я не заслуживаю ни насмешек, ни презрения»: профессиональный статус женщин в мире журналистики второй половины XIX в. по материалам их эго-документов
No full textThis article explores the perception of the professional status of Russian female journalists in the second half of the 19th century. The main sources are ego-documents of women at periodicals working during the period under study, as well as those who identified as journalists. One of the most frequent elements of the analysed memoir texts is the expression of the need to work at periodicals for material support and self-fulfilment. Most female journalists saw their labour as an option to serve society and were ready to make sacrifices for the cause. They emphasized respect and the value of their work in the eyes of their colleagues, ridiculing and denouncing cases of gender discrimination. Women’s limited access to higher education stands out as a significant issue in the ego-documents.L’article explore la perception que les femmes journalistes russes de la seconde moitié du XIXe siècle avaient de leur statut professionnel. Ses principales sources sont des ego-documents émanant d’employées de périodiques qui s’identifiaient elles-mêmes comme journalistes et dont les activités professionnelles relevaient de la période étudiée. Dans les textes mémoriels analysés, la nécessité de travailler dans la presse est fréquemment justifiée par des besoins matériels ainsi que par la quête de soi. La majorité des femmes journalistes considéraient leur travail comme une forme de service rendu à la société et étaient prêtes à faire des sacrifices au nom de cette « Cause ». Elles soulignaient le respect et l’estime de leur travail par leurs collègues, ridiculisaient et dénonçaient les cas de discrimination de genre. Dans ces ego-documents, l’accès limité des femmes à l’enseignement supérieur est présenté comme un problème important.В статье охарактеризовано восприятие русскими журналистками второй половины XIX века своего профессионального статуса. Основными источниками стали эго-документы сотрудниц периодики, чья профессиональная деятельность пришлась на исследуемый период, а также идентифицирующих себя в качестве журналисток. Одним из часто встречающихся элементов проанализированных мемуарных текстов является объяснение необходимости работы в органах периодической печати для материального обеспечения и самореализации. Большинство из журналисток рассматривали свой труд как вариант служения обществу и были готовы идти на жертвы ради «Дела». Они подчеркивали уважение и ценность своего труда в глазах коллег, высмеивая и обличая случаи дискриминации по гендерному признаку. Значимой проблемой в эго-документах предстает ограниченный доступ для женщин к высшему образованию
A Framework for Universality in Physics, Computer Science, and Beyond
No full textTuring machines and spin models share a notion of universality according towhich some simulate all others. Is there a theory of universality that capturesthis notion? We set up a categorical framework for universality which includesas instances universal Turing machines, universal spin models, NP completeness,top of a preorder, denseness of a subset, and more. By identifying necessaryconditions for universality, we show that universal spin models cannot befinite. We also characterize when universality can be distinguished from atrivial one and use it to show that universal Turing machines are non-trivialin this sense. Our framework allows not only to compare universalities withineach instance, but also instances themselves. We leverage a Fixed Point Theoreminspired by a result of Lawvere to establish that universality and negationgive rise to unreachability (such as uncomputability). As such, this work setsthe basis for a unified approach to universality and invites the study offurther examples within the framework.Comment: 66 pages, 12 figures, many diagrams. v3: DOI change
Isolated Suborders and their Application to Counting Closure Operators
No full textIn this paper we investigate the interplay between isolated suborders andclosures. Isolated suborders are a special kind of suborders and can be used todiminish the number of elements of an ordered set by means of a quotientconstruction. The decisive point is that there are simple formulae establishingrelationships between the number of closures in the original ordered set andthe quotient thereof induced by isolated suborders. We show how theseconnections can be used to derive a recursive algorithm for counting closures,provided the ordered set under consideration contains suitable isolatedsuborders
A Session Type System for Asynchronous Unreliable Broadcast Communication
No full textSession types are formal specifications of communication protocols, allowingprotocol implementations to be verified by typechecking. Up to now, sessiontype disciplines have assumed that the communication medium is reliable, withno loss of messages. However, unreliable broadcast communication is common in awide class of distributed systems such as ad-hoc and wireless sensor networks.Often such systems have structured communication patterns that should beamenable to analysis by means of session types, but the necessary theory hasnot previously been developed. We introduce the Unreliable Broadcast SessionCalculus, a process calculus with unreliable broadcast communication, and equipit with a session type system that we show is sound. We capture two commonoperations, broadcast and gather, inhabiting dual session types. Message lossmay lead to non-synchronised session endpoints. To further account forunreliability we provide with an autonomous recovery mechanism that does notrequire acknowledgements from session participants. Our type system ensuressoundness, safety, and progress between the synchronised endpoints within asession. We demonstrate the expressiveness of our framework by implementingPaxos, the textbook protocol for reaching consensus in an unreliable,asynchronous network
Constructing Deterministic Parity Automata from Positive and Negative Examples
No full textWe present a polynomial time algorithm that constructs a deterministic parityautomaton (DPA) from a given set of positive and negative ultimately periodicexample words. We show that this algorithm is complete for the class of-regular languages, that is, it can learn a DPA for each regular-language. For use in the algorithm, we give a definition of a DPA,that we call the precise DPA of a language, and show that it can be constructedfrom the syntactic family of right congruences for that language (introduced byMaler and Staiger in 1997). Depending on the structure of the language, theprecise DPA can be of exponential size compared to a minimal DPA, but it canalso be a minimal DPA. The upper bound that we obtain on the number of examplesrequired for our algorithm to find a DPA for is therefore exponential inthe size of a minimal DPA, in general. However we identify two parameters ofregular -languages such that fixing these parameters makes the boundpolynomial.Comment: 47 pages, TheoretiCS articl
On harmonious coloring of hypergraphs
No full textA harmonious coloring of a -uniform hypergraph is a vertex coloringsuch that no two vertices in the same edge have the same color, and each-element subset of colors appears on at most one edge. The harmonious number is the least number of colors needed for such a coloring. The paper contains a new proof of the upper bound onthe harmonious number of hypergraphs of maximum degree with edges.We use the local cut lemma of A. Bernshteyn
On Tools for Completeness of Kleene Algebra with Hypotheses
No full textIn the literature on Kleene algebra, a number of variants have been proposedwhich impose additional structure specified by a theory, such as Kleene algebrawith tests (KAT) and the recent Kleene algebra with observations (KAO), or makespecific assumptions about certain constants, as for instance in NetKAT. Manyof these variants fit within the unifying perspective offered by Kleene algebrawith hypotheses, which comes with a canonical language model constructed from agiven set of hypotheses. For the case of KAT, this model corresponds to thefamiliar interpretation of expressions as languages of guarded strings. Arelevant question therefore is whether Kleene algebra together with a given setof hypotheses is complete with respect to its canonical language model. In thispaper, we revisit, combine and extend existing results on this question toobtain tools for proving completeness in a modular way. We showcase these toolsby giving new and modular proofs of completeness for KAT, KAO and NetKAT, andwe prove completeness for new variants of KAT: KAT extended with a constant forthe full relation, KAT extended with a converse operation, and a version of KATwhere the collection of tests only forms a distributive lattice
Summing the sum of digits
No full textWe revisit and generalize inequalities for the summatory function of the sumof digits in a given integer base. We prove that several known results can bededuced from a theorem in a 2023 paper by Mohanty, Greenbury, Sarkany,Narayanan, Dingle, Ahnert, and Louis, whose primary scope is the maximummutational robustness in genotype-phenotype maps.Comment: 10 pages; this is a revised version to appear in Communications in Mathematic
Set-theoretical solutions to the pentagon equation: a survey
No full textThis survey aims to collect the main results of the theory of theset-theoretical solutions to the pentagon equation obtained up to now in theliterature. In particular, we present some classes of solutions and raise somequestions