Episciences.org
Not a member yet
6707 research outputs found
Sort by
On birational automorphisms of Severi-Brauer surfaces
No full textThe generators of the group of birational automorphisms of any Severi-Brauersurface non-isomorphic over an algebraically non-closed field to the projectiveplane are explicitly described.Comment: Revised versio
Self-stabilisation of cellular automata on tilings
No full textGiven a finite set of local constraints, we seek a cellular automaton (i.e.,a local and uniform algorithm) that self-stabilises on the configurations thatsatisfy these constraints. More precisely, starting from a finite perturbationof a valid configuration, the cellular automaton must eventually fall back intothe space of valid configurations where it remains still. We allow the cellularautomaton to use extra symbols, but in that case, the extra symbols can alsoappear in the initial finite perturbation. For several classes of localconstraints (e.g., -colourings with , and North-East deterministicconstraints), we provide efficient self-stabilising cellular automata with orwithout additional symbols that wash out finite perturbations in linear orquadratic time, but also show that there are examples of local constraints forwhich the self-stabilisation problem is inherently hard. We note that theoptimal self-stabilisation speed is the same for all local constraints that areisomorphic to one another. We also consider probabilistic cellular automatarules and show that in some cases, the use of randomness simplifies theproblem. In the deterministic case, we show that if finite perturbations arecorrected in linear time, then the cellular automaton self-stabilises evenstarting from a random perturbation of a valid configuration, that is, whenerrors in the initial configuration occur independently with a sufficiently lowdensity.Comment: 56 pages, 28 figure
Applying Data Structure Succinctness to Graph Numbering For Efficient Graph Analysis
No full textGraph algorithms have inherent characteristics, including data-driven computations and poor locality. These characteristics expose graph algorithms to several challenges, because most well studied (parallel) abstractions and implementation are not suitable for them. In our previous work [21, 22, 24], we show how to use some complex-network properties, including community structure and heterogeneity of node degree, to improve performance, by a proper memory management (Cn-order) and an appropriate thread scheduling (comm-deg-scheduling). In recent work [23], Besta et al. proposed log(graph), a graph representation that outperforms existing graph compression algorithms. In this paper, we show that our graph numbering heuristic and our scheduling heuristics can be improved when they are combined with log(graph) data structure. Experiments were made on multi-core machines. For example, on one node of a multi-core machine (Troll from Grid'5000), we showed that when combining our previously proposed heuristics with graph compression, with Pagerank being executing on Live Journal dataset, we can reduce with cn-order: cache-references from 29.94% (without compression) to 39.56% (with compression), cache-misses from 37.87% to 51.90% and hence time from 18.93% to 28.66%
Residuality and Learning for Nondeterministic Nominal Automata
No full textWe are motivated by the following question: which data languages admit anactive learning algorithm? This question was left open in previous work by theauthors, and is particularly challenging for languages recognised bynondeterministic automata. To answer it, we develop the theory of residualnominal automata, a subclass of nondeterministic nominal automata. We provethat this class has canonical representatives, which can always be constructedvia a finite number of observations. This property enables active learningalgorithms, and makes up for the fact that residuality -- a semantic property-- is undecidable for nominal automata. Our construction for canonical residualautomata is based on a machine-independent characterisation of residuallanguages, for which we develop new results in nominal lattice theory. Studyingresiduality in the context of nominal languages is a step towards a betterunderstanding of learnability of automata with some sort of nondeterminism
The Mori fan of the Dolgachev-Nikulin-Voisin family in genus
No full textIn this paper we study the Mori fan of the Dolgachev-Nikulin-Voisin family indegree as well as the associated secondary fan. The main result is anenumeration of all maximal dimensional cones of the two fans.Comment: Substantially revised final versio
L'épreuve du tri sur site des déchets de la construction
No full textÉpisciencesThe transformation of the construction sector is of utmost importance to diminish the material footprint of our societies, as it remains the main source of waste generation in many regions worldwide. Yet, construction waste is often mixed on construction sites, and only sorted out afterwards in centralised units, which largely impedes potential material recovery. The implementation of on-site sorting strategies is thereby crucial, although its development does not follow the environmental benefits that are associated with them. This poor diffusion of on-site sorting for construction waste reveals a poor knowledge of the reality of sorting practices on construction sites, which remains an academic and operational blackbox. Through an embedded research within a medium-size French construction company, this article documents the poor practices of sorting construction waste. This phenomenon is often associated with doubts, uncertainties and preconceptions regarding the economic viability of on-site sorting. This paper provides a simple model to test this preconceived idea and the economic interest of on-site sorting, showing that it results in the diminution of waste treatment costs by up to 48% for construction companies. One such result is contrasted with the monitoring of two experiments, where on-site sorting practices are developed, showing the important challenges this operationalisation entails to make the economic interest and the sustainability of the approach converge and coincide.La transformation du secteur de la construction, plus gros producteur de déchets dans de nombreux pays, représente un enjeu majeur pour une diminution de l'empreinte matérielle de nos sociétés. Cependant, les déchets sont souvent mélangés sur les chantiers de construction, triés seulement a posteriori dans des unités centralisées, diminuant fortement la recyclabilité de certains matériaux. La mise en place de tri directement sur les chantiers de construction est ainsi un enjeu d'importance, dont la diffusion demeure décorrélée des bénéfices environnementaux qui lui sont associés. Cette faible diffusion du tri sur site révèle une faible connaissance des pratiques réelles de tri, qui reste une boîte noire opérationnelle comme académique. Cet article, via une recherche en partenariat avec une entreprise de la construction francilienne, permet de documenter la réalité des faibles pratiques de tri sur les chantiers de construction. Celle-ci est notamment associée à des doutes sur la viabilité économique de ce type de démarche. L'article propose une simulation simple pour tester l'intérêt économique du tri sur chantier, montrant une baisse des coûts de gestion des déchets pour les constructeurs jusqu'à 48%. Celle-ci est mise à l'épreuve de la mise en place dans deux chantiers, montrant les défis que celle-ci ouvrent pour confirmer à la fois l'intérêt économique et la soutenabilité de la démarche de tri sur site des déchets de la construction. Mots-clés : déchets-construction-tri sur site-pratiques professionnelles-Ile de Franc
Science paysagère au service de l'observatoire scientifique Sociétés-Milieux en appui à la gestion territoriale
No full textPour mener son action face à une problématique de société, le gestionnaire de territoire doit s’appuyer sur des informations pertinentes dans le temps et l’espace. Les observatoires selon le modèle OSAGE – Observatoire Scientifique en Appui à la GEstion territoriale s'intéressent tout particulièrement aux relations Sociétés-Milieux et peuvent seconder le gestionnaire. Ce travail montre en quoi la méthode OSYPCA d’analyse paysagère et le cadre formel sur lequel elle s’appuie informent sur le milieu et la relation société-milieu et sont utiles aux trois piliers d'un observatoire OSAGE : exigence scientifique, continuité temporelle et ancrage territorial. L’analyse d’une expérience de terrain sur l’île de La Réunion illustre son potentiel à produire une information pertinente même si la connaissance préalable est réduite, à appréhender les dynamiques spatio-temporelles, sans nécessité d’investissements lourds et enfin à mettre en dialogue les disciplines scientifiques entre elles mais aussi les scientifiques avec les acteurs du territoire
Inference Systems with Corules for Combined Safety and Liveness Properties of Binary Session Types
No full textMany properties of communication protocols combine safety and livenessaspects. Characterizing such combined properties by means of a single inferencesystem is difficult because of the fundamentally different techniques(coinduction and induction, respectively) usually involved in defining andproving them. In this paper we show that Generalized Inference Systems allow usto obtain sound and complete characterizations of (at least some of) thesecombined inductive/coinductive properties of binary session types. Inparticular, we illustrate the role of corules in characterizing fairtermination (the property of protocols that can always eventually terminate),fair compliance (the property of interactions that can always be extended toreach client satisfaction) and fair subtyping, a liveness-preserving refinementrelation for session types. The characterizations we obtain are simplercompared to the previously available ones and corules provide insight on theliveness properties being ensured or preserved. Moreover, we can convenientlyappeal to the bounded coinduction principle to prove the completeness of theprovided characterizations
La traduction littéraire automatique : Adapter la machine à la traduction humaine individualisée
No full textLa traduction automatique neuronale et son adaptation à des domaines spécifiques par le biais de corpus spécialisés ont permis à cette technologie d’intégrer bien plus largement qu’auparavant le métier et la formation des traducteur·trice·s. Si le paradigme neuronal (et le deep learning de manière générale) a ainsi pu investir des domaines parfois insoupçonnés, y compris certains où la créativité est de mise, celui-ci est moins marqué par un gain phénoménal de performance que par une utilisation massive auprès du public et les débats qu’il génère, nombre d’entre eux invoquant couramment le cas littéraire pour (in)valider telle ou telle observation. Pour apprécier la pertinence de cette technologie, et ce faisant surmonter les discours souvent passionnés des opposants et partisans de la traduction automatique, il est toutefois nécessaire de mettre l’outil à l’épreuve, afin de fournir un exemple concret de ce que pourrait produire un système entraîné spécifiquement pour la traduction d’œuvres littéraires. Inscrit dans un projet de recherche plus vaste visant à évaluer l’aide que peuvent fournir les outils informatiques aux traducteurs et traductrices littéraires, cet article propose par conséquent une expérience de traduction automatique de la prose qui n’a plus été tentée pour le français depuis les systèmes probabilistes et qui rejoint un nombre croissant d’études sur le sujet pour d’autres paires de langues. Nous verrons que si les résultats sont encourageants, ceux-ci laissent présager une tout autre manière d’envisager la traduction automatique, plus proche de la traduction humaine assistée par ordinateur que de la post-édition pure, et que l’exemple des œuvres de littérature soulève en outre des réflexions utiles pour la traduction dans son ensemble
Small Promise CSPs that reduce to large CSPs
No full textFor relational structures A, B of the same signature, the Promise ConstraintSatisfaction Problem PCSP(A,B) asks whether a given input structure mapshomomorphically to A or does not even map to B. We are promised that the inputsatisfies exactly one of these two cases. If there exists a structure C with homomorphisms , thenPCSP(A,B) reduces naturally to CSP(C). To the best of our knowledge all knowntractable PCSPs reduce to tractable CSPs in this way. However Barto showed thatsome PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to finite C is possible, thisstructure may become arbitrarily large. For every integer and every primep we give A, B of size n with a single relation of arity such thatPCSP(A, B) reduces via a chain of homomorphisms to a tractableCSP over some C of size p but not over any smaller structure. In a secondfamily of examples, for every prime we construct A, B of size with a single ternary relation such that PCSP(A, B) reduces via to a tractable CSP over some C of size p but not over any smaller structure. Incontrast we show that if A, B are graphs and PCSP(A,B) reduces to tractableCSP(C) for some finite digraph C, then already A or B has a tractable CSP. Thisextends results and answers a question of Deng et al