ED Mathématiques et Informatique
Fast approximation algorithms for formal languages
by Gabriel BATHIE (LaBRI - Laboratoire Bordelais de Recherche en Informatique)
The defense will take place at 14h00 - Amphitéatre du LaBRI Laboratoire Bordelais de Recherche en Informatique (LaBRI) Bâtiment A30 351, cours de la Libération, F-33405 Talence cedex
in front of the jury composed of
- Nathanaël FIJALKOW - Directeur de recherche - Université de Bordeaux - Directeur de these
- Frédéric MAGNIEZ - Directeur de recherche - IRIF - Rapporteur
- Michal KOUCKY - Professor - Charles University - Rapporteur
- Inge LI GORTZ - Professor - Technical University of Denmark - Examinateur
- Raluca URICARU - Maîtresse de conférences - Université de Bordeaux - Examinateur
- Charles PAPERMAN - Maître de conférences - Université de Lille - Examinateur
Since the 70's, computer scientists have developed very efficient tools and algorithms for text processing. However, these techniques are mostly focused on exact problems, and cannot be straightforwardly adapted to approximation tasks, or do not scale to the size of modern datasets. In this thesis, we study resource-efficient approximation algorithms for text processing. The first part of this thesis studies variants of approximate pattern matching, tasks where one must find all substrings of a text that are similar to the given pattern, for various notions of similarity. We first investigate the case circular pattern matching. We give a data structure with a time-space trade-off in the read-only model for internal pattern matching, and use it to solve circular pattern matching and the longest common substring problem with little additional space in the read-only model. Next, we consider the case of similarity measured by the Hamming distance, in strings with wildcards, that is, characters that match any other character. Focusing on the low-distance regime and on the case of strings with few contiguous groups of wildcards, we give an efficient algorithm and a combinatorial characterization of the structure of occurrences in this setting. We give a lower bound that shows that our characterization is close to optimal. Finally, we study data structures for computing longest common extensions in string with wildcards (LCEW). We give a data structure that provide a time-space trade-off in the read-only model, and use it to derive efficient algorithms for pattern matching in and analysis of string with wildcards. We also show a connection to sparse Boolean matrix multiplication, from which we derive lower bounds for combinatorial data structures for LCEW. The second part of this thesis studies the task of deciding approximate membership in a formal language, in three different frameworks. We start with the Property Testing, the framework of information-efficient algorithms, in our case for regular languages, following the seminal work of Alon, Krivelevich, Newman and Szegedy [SIAM J. Comp. 99]. We give a complete characterization of the complexity of testing regular languages under the Hamming distance, showing that any regular language belongs to one of three complexity classes, and that these classes can be characterized using combinatorial objects, called minimal blocking sequences. We further show that this characterization is effective: given a finite automaton, deciding to which class it belongs to is complete for PSPACE. Next, we turn to the question of computing the Hamming or edit distance between an input word and a given language. We give small-space algorithms in the read-only or streaming model for the low-distance version of these problems, for languages of palindromes and of squares. Finally, we design a small-space algorithm for computing the palindromic length of a string in the read-only model. Our algorithm is based on novel results on the structure of the k-palindromic prefixes of a string, i.e., its prefixes of palindromic length k.
ED Droit
Naming the United Kingdom: The Classification of Political Forms Through the Lens of British, French, and Canadian Scholarly Traditions
by Lucien CARRIER (CENTRE D'ÉTUDES ET DE RECHERCHES COMPARATIVES SUR LES CONSTITUTIONS, LES LIBERTÉS ET L'ÉTAT)
The defense will take place at 14h00 - 1J Pôle juridique et judiciaire de l'université de Bordeaux 35, place Pey-Berland bordeaux 33000 Bordeaux
in front of the jury composed of
- Marie-Claire PONTHOREAU-LANDI - Full professor - Université de Bordeaux - Directeur de these
- Jean-François GAUDREAULT-DESBIENS - Full professor - Université de Montréal - Rapporteur
- Yseult MARIQUE - Full professor - University of Essex - Rapporteur
- Johanne POIRIER - Full professor - McGill - CoDirecteur de these
- Thomas PERROUD - Professeur des universités - Paris II-Assas - Examinateur
This thesis investigates how the United Kingdom's constitutional classification varies within British, French, and Canadian scholarly traditions. It examines the academic discourses prevalent within each tradition, particularly through recommended reading lists and constitutional law textbooks. The study reveals how the UK's political form—complex and continually evolving—is interpreted differently depending on academic and scholarly contexts, thereby uncovering implicit frameworks, methodological biases, and epistemological particularities. Employing a reflexive comparative perspective, this research highlights the conditions that enable constitutional knowledge and critically assesses classification itself as an intellectual endeavor. Thus, the United Kingdom, resisting traditional categorization, serves as an ideal lens to explore distinct classificatory logics inherent in each scholarly tradition.
ED Entreprise Economie Société
Identification, assessment, and impacts of benevolent leadership in contexts of spatial mobility and hybrid de-spatialization of workplaces
by Yann ARNAUD (IRGO - Institut de Recherche en Gestion des Organisations)
The defense will take place at 9h30 - Salle 107 Pôle universitaire des sciences de gestion de l'Université de Bordeaux, Bâtiment C , 35 Avenue Abadie, 33000 Bordeaux
in front of the jury composed of
- Laila BENRAISS-NOAILLES - Professeure des universités - Université de Bordeaux - Directeur de these
- Julien CUSIN - Professeur des universités - Université de Bordeaux - CoDirecteur de these
- Catherine VIOT - Professeure des universités - Université de Bordeaux - Examinateur
- Sylvie GUERRERO - Professeure des universités - Université du Quebec à Montréal - Examinateur
- Karim MIGNONAC - Professeur des universités - Université Toulouse Capitole - Rapporteur
- Marc VALAX - Professeur des universités - Université Côte d'Azur - Rapporteur
Benevolent leadership is an established concept in leadership research. While its impacts have been extensively documented in face-to-face settings, the widespread adoption of hybrid work, characterized by the phenomena of spatial mobility and de-spatialization, raises questions regarding the validity of traditional theories and their applicability in these new work environments. This thesis investigates the identification, assessment, and impacts of benevolent leadership on employees in contexts of spatial mobility and hybrid de-spatialization of workplaces. A mixed-methods approach was conducted through five sequential studies. Study 1 (N=40) identifies the characteristics of benevolent leadership as perceived by employees and generates a pool of items. Study 2 (N=19) assesses the face and content validity of these items with human resource management experts. Study 3 (N=228) purifies the items. Study 4 (N=456) confirms and validates a measurement scale. Study 5 (N=307) explores the impact of perceived benevolent leadership in hybrid work context. From a qualitative standpoint, benevolent leadership is a social influence process aimed at guiding attitudes, behaviors, and emotions toward the good, encapsulated within five paradigms: morality, spirituality, vitality, community, and mobility. From a quantitative standpoint, factorial analyses develop and validate a bi-dimensional measurement scale referred to as ELB-10. Drawing on social exchange theory, benevolent leadership is positively associated with organizational citizenship behaviors and negatively correlated with turnover intentions, considering perceived work isolation and affective organizational commitment as both single and double mediating variables. Overall, this thesis contributes to the advancement of benevolent leadership theories by focusing on employees' perspective within hybrid work context. It highlights the limitations of existing measurement scales and proposes a reliable alternative, the ELB-10. Furthermore, social exchange theory and the norm of reciprocity are discussed and extended in light of their applicability to hybrid work. Finally, the positive impacts perceived by employees emphasize the critical role of benevolent leadership in maintaining or restoring the relationships with their leaders in these new work contexts.
ED Sociétés, Politique, Santé Publique
From urban movement to metropolitan movement, a comparison between Bordeaux, Grenoble and Nantes
by Marine LUCE (Centre Emile Durkheim)
The defense will take place at 13h00 - Erasme 11 allée Ausone 33600 Pessac
in front of the jury composed of
- Gilles PINSON - Professeur - Université de Bordeaux - Directeur de these
- Valérie SALA PALA - Professeure - Université Jean Monnet de Saint-Etienne - Examinateur
- Tommaso VITALE - Professeur - Sciences Po (Institut d'Etudes Politiques de Paris) - Rapporteur
- Héloise NEZ - Professeure - Université Paris Cité - Examinateur
- Mariona TOMAS - Professeure - Université de Barcelone - Examinateur
- Stéphane CADIOU - Professeur - Université Lumière Lyon 2 - Rapporteur
This thesis focuses on the effects of metropolisation on the development of urban movements in France. Although metropolises are often regarded as post-political or adhocratic spaces, certain mobilisations against urban projects shift their spatial and political scale by targeting the metropolis as both the focus and framework of their actions. These movements contribute to the production of new metropolitan frameworks and adapt their collective action strategies to the metropolitan context. The study of six mobilisations against urban projects across the metropolises of Nantes, Grenoble, and Bordeaux allows for the identification of the institutional, political, and activist characteristics unique to each metropolis, which either facilitate or constrain the scaling up of these movements. This shift in scale is explained by the existence of a metropolitan activist milieu, as well as metropolitan political opportunity structures that are conducive to the rescaling of these mobilisations. In this way, we demonstrate how the metropolises of Nantes, Grenoble, and Bordeaux provide differentiated conditions for the emergence of the rescaling of the movements under study.