Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
Algorithmes incrémentaux pour le calcul de l'ensemble des ensembles de périodes
No full textOverlaps between words are crucial in many areas of computer science, such as code design, stringology, and bioinformatics. A self overlapping word is characterized by its periods and borders. A period of a word u is the starting position of a suffix of u that is also a prefix u, and such a suffix is called a border. Each word of length, say n > 0, has a set of periods, but not all combinations of integers are sets of periods. Computing the period set of a word u takes linear time in the length of u. We address the question of computing, the set, denoted Γn , of all period sets of words of length n. Although period sets have been characterized, there is no formula to compute the cardinality of Γn (which is exponential in n), and the known dynamic programming algorithm to enumerate Γn suffers from its space complexity. We present an incremental approach to compute Γn from Γn−1 , which reduces the space complexity, and then a constructive certification algorithm useful for verification purposes. The incremental approach defines a parental relation between sets in Γn−1 and Γn , enabling one to investigate the dynamics of period sets, and their intriguing statistical properties. Moreover, the period set of a word u is key for computing the absence probability of u in random texts. Thus, knowing Γn is useful to assess the significance of word statistics, such as the number of missing words in a random text.Les chevauchements entre chaînes de caractères sont cruciaux dans de nombreux domaines de l'informatique, tels que la bio-informatique, la conception de codes et l'algorithmique du texte. Une chaîne qui se chevauche elle-même est caractérisée par ses périodes et ses bordures. Une période d'une chaîne u est la position de départ d'un suffixe de u qui est aussi un préfixe u, et un tel suffixe est nommé bordure. Chaque mot de longueur, disons n > 0, possède un ensemble de périodes, mais toutes les combinaisons d'entiers ne sont pas des ensembles de périodes. La question que nous nous posons est de savoir comment calculer l'ensemble, noté Γn , de tous les ensembles de périodes des chaînes de longueur n. Calculer l'ensemble de périodes pour tous les mots possibles de longueur n est clairement prohibitif, puisque la cardinalité de Γn est exponentielle en n. Un algorithme de programmation dynamique existe pour énumérer Γn, mais il souffre d'une complexité spatiale trop coûteuse. Après avoir énoncé quelques propriétés combinatoires des ensembles de périodes, nous présentons des algorithmes qui calculent Γn à partir de Γn-1, pour toute longueur n > 1. L'ensemble de périodes d'une chaîne de caractères u est une information clé pour calculer la probabilité d'absence de u dans des textes aléatoires. Par conséquent, le calcul de Γn est utile pour évaluer l'importance des statistiques sur les mots, telles que le nombre de k-mers manquants dans un texte aléatoire ou le nombre de k-mers communs à deux textes aléatoires. Outre ses applications, l'étude de Γn est intéressante en soi car elle révèle les propriétés combinatoires des chevauchements de chaînes de caractères
Decoding Attack Behaviors by Analyzing Patterns in Instruction-Based Attacks using Gem5
No full textInternational audienceThe diversity of Instruction Set Architectures (ISAs), each with unique limitations and optimization strategies, presents both opportunities and challenges in processor design. Modern processor vendors leverage these ISAs to enhance security, reliability, and performance. Recent security vulnerabilities, notably Spectre and Meltdown, have underscored the importance of robust hardware security measures. The recent discovery of attacks such as Specter and Meltdown had a high impact on the vendors regarding hardware security. Processor micro-architectures are susceptible to side-channel attacks, which exploit information leakage to identify vulnerabilities. Techniques such as speculative execution and branch prediction, commonly employed by processors from AMD, Intel, and ARM, while beneficial for performance optimization, inadvertently create avenues for such attacks. Additionally, the practice of out-of-order execution, designed to maximize efficiency, can be manipulated to form side channels, further compromising security. Additionally, shared memory resources, particularly cache memory, are another vector for attack. By analyzing access patterns to shared caches, attackers can construct cache-based side channels, facilitating sophisticated attacks like FLUSH+Reload and Prime+Probe.In response to these threats, this work proposes a comprehensive mechanism for securing processor micro-architectures against side-channel attacks. Our methodology comprises five stages:(1) identifying and developing attack vectors, (2) compiling these attacks across various architectures, (3) scripting simulations using the Gem5 tool, (4) running these simulations, and (5) analyzing the resultant attack traces to understand and mitigate vulnerabilities. These stages are detailed in the next paragraphs
NIRS as a high-throughput phenotyping tool for assessing the diversity of leaf functioning under water deficit in a large grapevine panel
No full textLes présentations effectuées lors des rencontres sont disponibles en PDF, pour les auteurs qui ont donné l’autorisation de les diffuser.International audienceWater resource is a major limiting factor impacted by climate change, threatening the yield and quality of grapevine production. Understanding the ecophysiological mechanisms involved in response to water deficit is crucial to select new varieties more drought-tolerant. A major bottleneck that hampers such advances is the lack of methods for measuring functioning traits on thousands of leaves as required for genetic analyses. Recent studies have highlighted the interest of near-infrared spectroscopy (NIRS) and chlorophyll fluorescence for high-throughput evaluation of leaf functioning traits. The aim of this study is to develop these methods, and test their robustness to facilitate their deployment for phenotyping the genetic diversity of grapevine. 246 genotypes, representative of the genetic diversity of the species Vitis vinifera, were phenotyped over two consecutive years. In 2021, the genotypes were grown in pots outdoors under non-limiting irrigation conditions, while in 2022, the same potted genotypes were subjected to three different water scenarios (i. Well-watered, ii. Moderate water deficit, iii. Severe water deficit) in a greenhouse (PhenoArch high-throughput phenotyping platform). To evaluate traits related to carbon and water functioning across the entire panel, a subset of genotypes were phenotyped by combining i/ low-throughput devices to precisely measure cophysiological traits, and ii/ innovative high-throughput portable devices to measure NIRS, porometry and chlorophyll fluorescence. These data enabled the creation of partial least squares regression (PLSR) models using both low- and high-throughput data to predict ecophysiological traits. Leaf mass per area and leaf water content were well predicted by spectrometers (R² > 0.7). Photosynthesis, on the other hand, was well predicted by chlorophyll fluorescence and porometry data. The robustness of the predictive models was tested between experiments by comparing models calibrated with data from one experiment to predict data from the second one. The robustness of the models was dependent on the trait and the high-throughput device used. The prediction of leaf mass per area, using NIRS, appeared to be accurate and stable between experiments. Intra-experiment robustness analysis showed that water deficit can impact the quality of trait predictions, particularly those related to water, such as water content and water use efficiency. The R² and RMSE parameters provided additional information, especially as water deficit affected trait variability. The prediction of these traits was less accurate when applied on a plant that had been grown under severe water deficit. Compelling models will be employed to predict these traits across the entire panel, enabling their use in genetic analysis
On the Complexity of the Median and Closest Permutation Problems
No full textInternational audienceGenome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. On the other hand, finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations of distinct integers, some distance metrics have been extensively studied. We investigate the median and closest problems on permutations over the following metrics: breakpoint distance, swap distance, block-interchange distance, short-block-move distance, and transposition distance. In biological applications some values are usually very small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation regarding some metrics of distance, even for only k = 3 permutations; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics when parameterized by the target distance d
Combining artificial intelligence and co-design to build scenarios for an agroecological transition of farming systems
No full textInternational audienceIntroductionTo address agricultural challenges, engaging agroecological transition is crucial, necessitating a redesign strategy for productive and resilient biodiversity-based farming systems. However, implementing spatio-temporal design of diversified systems is complex due to the diverse factors that need to be considered, the large number of possible crops combinations in time and space, and the need to combine different forms of knowledge to take account of operational constraints, soil and climate conditions, and agroecological objectives. To support the design of agroecological cropping systems, we propose to combine together AI (constraint programming) which provides formalisms with a high level of expressivity (Challand et al., 2023) with co-design approaches that enable stakeholders with diverse skills and knowledge to collaborate, while putting the farmer at the centre of the design ecosystem. This approach has been applied to one of the most complex agrosystems, the mixed orchard market gardens, to explore crop allocation scenarios with the farmer that take tree growth into account.Materials, methodsThe model AGROECOPLAN, used in this study to generates a spatio-temporal crop allocation solution, has been described in Challand et al (2023). The model is composed of four sets of constraints to take into account pedoclimatic, operational and agroecological constraints: respect the return time of crops, forbid negative spatial interactions (spread of pests, incompatible cultivation operations, shade from neighbouring crops or trees…), forbid unfavourable precedents, forbid impossible locations. The model then optimizes two criteria to propose a cropping plan that maximizes the positive spatial and temporal interactions between crops.The model was used in a case study one-hectare micro-farm in South of France. The objective was to assign the 60 crops from the cropping calendar to the 80 cropping beds, considering the crop assignments of the last 3 years and the farm's pattern. The co-design workshops were conducted in three steps : (i) identify and formalise the problem through a semi-directive interview with the farmers (ii) run the AGROECOPLAN model to propose a crop allocation scenario (iii) evaluate with the farmer the model's output and performance. If the solution is deemed unsatisfactory, the set of constraints is modified with the farmers to better specify the problem and the model is run again (repeating step 2) until a satisfactory solution is found.ResultsThe co-design workshops led farmers to formulate three issues that guided the exploration of the scenarios. (i) How to add the maximum green manure beds to improve the agroecosystem performances? (ii) How will the growth of fruit trees change the layout of crops in the future? (iii) What crop area is needed to satisfy all the farmers' expectations? The model was able to find solutions that satisfied all the constraints for each of these three issues. This required several iterations each time to better specify and prioritize the constraints.To answer the first question, two green manures were selected with the farmers: fodder beet and forage rye. By maximizing the number of green manures, 10 fodder beet beds and 24 forage rye beds were introduced, increasing the total number of positive interactions between crops by 16%. By taking into account the growth of the trees, we have been able to adapt the cultivation plan over long time, allowing crops that need or tolerate shade to benefit from it. Finally, exploration of the scenarios to answer the third question showed that 7 additional cropping beds were needed to find a cropping plan that met all the farmers' expectations. This corresponds to a 9% increase in cultivated area, which was feasible in this case study.DiscussionBy integrating constraint programming into a co-design approach, we effectively managed the complex combinatorial nature of designing highly diversified farming systems and took account of farm-specific constraints and farmer expectations. This process introduced a disruptive solution for farmers, providing a basis for discussion on how to evolve their practices in order to strike a balance between integrating agroecological principles and maintaining acceptable operational management. This makes it possible to integrate many internal (soil-plant interactions) and external (management practices, climate) regulations that underpin the resilience of agro-ecosystems.ReferencesChalland, M., Vismara, P., Justeau-Allaire, D., and de Tourdonnet, S. (2023). Supporting Sustainable Agroecological Initiatives for Small Farmers through Constraint Programming. In "Proceedings IJCAI-23, Macao, S.A.R
Explainable epidemiological thematic features for event based disease surveillance
No full textInternational audienceEvent based disease surveillance (EBS) systems are biosurveillance systems that have the ability to detect and alert on (re)-emerging infectious diseases by monitoring acute public or animal health event patterns from sources such as blogs, online news reports and curated expert accounts. These information rich sources, however, are largely unstructured text data requiring novel text mining techniques to achieve EBS goals such as epidemiological text classification. The main objective of this research was to improve epidemiological text classification by proposing a novel technique of enriching thematic features using a weak supervision approach. In our approach, we train and test a mixed domain language model named EpidBioELECTRA to first enrich thematic features which are then used to improve epidemiological text classification. We train EpidBioELECTRA on a large dataset which we create consisting of 70,700 annotated documents that includes 70,400 labeled thematic features. We empirically compare EpidBioELECTRA with both general purpose language models and domain specific language models in the task of epidemiological corpus classification. Our findings shows that epidemiological classification systems work best with language models pre-trained using both epidemiological and biomedical corpora with a continual pre-training strategy. EpidBioELECTRA improves epidemiological document classification by 19.2 score points as compared to its vanilla implementation BioELECTRA. We observe this by the comparison of BioELECTRA verses EpidBioELECTRA on our most challenging dataset PADI-Web where our approach records 92.33 precision score, 94.62 recall score and 93.46 score. We also experiment the impact of increasing context length of train documents in epidemiological document classification and found out that this improves the classification task by 7.79 score points as recorded by EpidBioELECTRA’s performance. We also compute Almost Stochastic Order (ASO) scores to track EpidBioELECTRA’s statistical dominance. In addition, we carry out ablation studies on our proposed thematic feature enrichment approach using explainable AI techniques. We present explanations for the most critical thematic features and how they influence epidemiological classification task We found out that biomedical features (such as mentions of names of diseases and symptoms) are the most influential while spatio-temporal features (such as the mention of date of a given disease outbreak) are the least influential in epidemiological document classification. Our model can easily be extended to fit other domains
Cutoff Frequency Adjustment for FFT-Based Anomaly Detectors
No full textInternational audienceThis article presents a time series anomaly detection method based on the Fast Fourier Transform (FFT) using a high-pass filter. The proposed method aims to remove low-frequency components, such as trends and seasonality, which represent the normal behavior of the series, while preserving high-frequency components associated with anomalies. The major challenge in constructing this method lies in determining the high-pass filter's cutoff frequency without prior knowledge of the intrinsic nature of the series. In addition to the traditional approach, four new distinct approaches were explored to determine the high-pass filter's cutoff frequency, making the method adaptable to various datasets. Experimental results show the effectiveness of the method in anomaly detection using high-pass FFT filters that have a cutoff frequency adjusted by change points, outperforming traditional techniques such as statistical and machine learning methods in terms of F1 score, precision, accuracy, and execution time
Diversity of leaf functioning under water deficit in a large grapevine panel: high throughput phenotyping and genetic analyses
No full textInternational audienceWater resource is a major limiting factor impacted by climate change that threatens grapevine production and quality. Understanding the ecophysiological mechanisms involved in the response to water deficit is crucial to select new varieties more drought tolerant. A major bottleneck that hampers such advances is the lack of methods for measuring fine functioning traits on thousands of plants as required for genetic analyses. This study aimed at investigating how water deficit affects the trade-off between carbon gains and water losses in a large panel representative of the Vitis vinifera genetic diversity. 250 genotypes were grown under 3 watering scenarios (well-watered, moderate and severe water deficit) in a high-throughput phenotyping platform. To assess traits related to carbon and water functioning on the whole panel, we deployed an original approach where 120 leaves of 40 genotypes were phenotyped combining low-throughput devices to precisely measure ecophysiological traits, as well as innovative, portable high-throughput devices to measure near infrared reflectance, porometry and chlorophyll fluorescence. These data allowed us to build cutting-edge statistical models, such as multiblock models, which jointly use data from different devices, for predicting ecophysiological traits. Models for predicting photosynthesis and transpiration were accurate enough to be applied on the entire panel, only measured with high-throughput devices. Such predictions highlighted a wide range of genotypic variability and contrasting responses to water deficit. Multi-traits and Multi-Environment Genome Wide Association Studies further revealed genomic regions associated with these responses, and underlying candidate genes are being investigated
Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters
No full textInternational audienceWe consider two games between two players Ann and Ben who build a word together by adding alternatively a letter at the end of a shared word. In the nonrepetitive game, Ben wins the game if he can create a square of length at least 4, and Ann wins if she can build an arbitrarily long word without Ben winning. In the erase-repetition game, whenever a square occurs the second part of the square is erased and the goal of Ann is still to build an arbitrarily long word (Ben simply wants to limit the size of the word in this game).Grytczuk, Kozik, and Micek showed that Ann has a winning strategy for the nonrepetitive game if the alphabet is of size at least 6 and for the erase-repetition game if the alphabet is of size at least 8. In this article, we lower these bounds to respectively 4 and 6. The bound obtained by Grytczuk et al. relied on the so-called entropy compression and the previous bound by Pegden relied on some particular version of the Lovász Local Lemma. We recently introduced a counting argument that can be applied to the same set of problems as entropy compression or the Lovász Local Lemma and we use our method here.For these two games, we know that Ben has a winning strategy when the alphabet is of size at most 3, so our result for the nonrepetitive game is optimal, but we are not able to close the gap for the erase-repetition game
A Novel 3D Reconstruction Sensor Using a Diving Lamp and a Camera for Underwater Cave Exploration
No full textInternational audienceAquifer karstic structures, due to their complex nature, present significant challenges in accurately mapping their intricate features. Traditional methods often rely on invasive techniques or sophisticated equipment, limiting accessibility and feasibility. In this paper, a new approach is proposed for a non-invasive, low-cost 3D reconstruction using a camera that observes the light projection of a simple diving lamp. The method capitalizes on the principles of structured light, leveraging the projection of light contours onto the karstic surfaces. By capturing the resultant light patterns with a camera, three-dimensional representations of the structures are reconstructed. The simplicity and portability of the equipment required make this method highly versatile, enabling deployment in diverse underwater environments. This approach is validated through extensive field experiments conducted in various aquifer karstic settings. The results demonstrate the efficacy of this method in accurately delineating intricate karstic features with remarkable detail and resolution. Furthermore, the non-destructive nature of this technique minimizes disturbance to delicate aquatic ecosystems while providing valuable insights into the subterranean landscape. This innovative methodology not only offers a cost-effective and non-invasive means of mapping aquifer karstic structures but also opens avenues for comprehensive environmental monitoring and resource management. Its potential applications span hydrogeological studies, environmental conservation efforts, and sustainable water resource management practices in karstic terrains worldwide