Conflicto regional, estado central y sociedad periférica en Bolivia y Perú : un análisis histórico comparado.

Cette thèse porte sur les conflits entre centres et périphéries à l’intérieur des pays. Ces dernières années, de nombreux États ont vu l'émergence de régions ou territoires qui défient leurs «centres» politiques. Ces disputes peuvent atteindre divers degrés d'affrontement, en allant des simples divisions électorales à la sécession d'une périphérie rebelle. Pourquoi certaines régions défient-elles ouvertement leur centre, tandis que d'autres ne le font pas? Dans quelles conditions les différences entre le centre et les périphéries sont-elles maîtrisées et circonscrites, et quelles sont celles qui les exacerbent? La thèse cherche à répondre à ces questions en analysant les cas de la Bolivie et du Pérou. En Bolivie, pendant les années 2000, le conflit régional a donné lieu à un clivage entre centre et périphérie; au Pérou, malgré les similitudes avec la Bolivie, un clivage similaire ne s’est pas déployé. Pourquoi cette différence? La thèse répond à la question par une analyse historique comparée. Elle suggère que les conflits entre le centre et les périphéries doivent s’analyser à partir de la combinaison de deux dimensions. La première est l’absence ou la présence d’élites régionales qui, à partir d'organisations et de mises en discours qu'elles rendent légitimes, définissent et représentent les revendications de la région et négocient avec l'État central. La deuxième dimension renvoie aux conditions structurelles de la région, en particulier l'importance des ressources naturelles et la taille de sa population. La thèse développe une analyse historique de la façon dont les deux dimensions ont évolué en Bolivie et au Pérou au cours de la seconde moitié du XX siècle. Cette analyse permet d’expliquer la divergence entre les résultats dans chacun des cas, et de suggérer des réflexions plus générales sur les relations entre les centres et les périphéries.

Analyse des figures féminines juives dans le roman québécois moderne et contemporain : L’avalée des avalés, La Québécoite et Hadassa

Ce mémoire est consacré à la construction des personnages féminins juifs dans trois romans modernes et contemporains de la littérature québécoise de langue française. Il se penche sur les romans L’avalée des avalés (1967) de Réjean Ducharme, La Québécoite (1983) de Régine Robin et Hadassa (2006) de Myriam Beaudoin. Les fonctions, les valeurs et les discours entourant la présence des figures féminines juives sont analysés par le biais des dialogues entre les lieux et l’espace de manière à cerner les marqueurs identitaires, culturels, sociaux, linguistiques et religieux. Nous avons cherché à inscrire ce mémoire dans le prolongement du chapitre portant sur la figure féminine juive de l’ouvrage pionnier Mythes et images du Juif au Québec (1977) de Victor Teboul. Teboul considère la figure féminine juive comme un personnage principalement secondaire et sexuel. Cette analyse, très ancrée dans les discours sociaux de la période de publication, mérite d’être revisitée avec un corpus plus élargi et plus contemporain. Pour ce faire, nous avons cerné les principaux vecteurs identitaires féminins juifs en analysant les discours entourant leur présence, les dialogues entre identité, culture, Histoire et société et les dynamiques entre espaces et lieux. Nous avons constaté que, en plus de sortir des stéréotypes, l’identité des figures féminines juives des trois romans est modelée en fonction de son rapport aux lieux et à l’espace. D’une judéité littéraire foncièrement iconoclaste, en passant par une judéité culturelle et mémorielle jusqu’à une judéité qui se veut le plus réaliste, les trois romans du corpus diffèrent largement par leur rapport à la judéité.

Intersectionality in Practice : The Politics of Inclusion in the Québécois Women's Movement

En tant qu'acteur important de la vie politique québécoise, le mouvement des femmes a réussi à garantir de nouveaux droits pour les femmes et a fortement contribué à améliorer leurs conditions de vie. Cependant, son incapacité à reconnaître et à prendre en compte les expériences particulières des femmes qui vivent de multiple discriminations a été critiquée entre autres par les femmes autochtones, les femmes de couleur, les femmes immigrantes, les lesbiennes et les femmes handicapées. Par exemple, dans les 40 dernières années, un nombre croissant de femmes immigrantes et racisées se sont organisées en parallèle au mouvement pour défendre leurs intérêts spécifiques. Dans ce mémoire, je me penche sur la façon dont le mouvement des femmes québécois a répondu à leurs demandes de reconnaissance et adapté ses pratiques pour inclure les femmes de groupes ethniques et raciaux minoritaires. Bien que la littérature sur l'intersectionalité ait fourni de nombreuses critiques des tentatives des mouvements sociaux d'inclure la diversité, seulement quelques recherches se sont penchées sur la façon dont les organisations tiennent compte, dans leurs pratiques et discours, des identités et intérêts particuliers des groupes qui sont intersectionnellement marginalisés. En me basant sur la littérature sur l'instersectionnalité et les mouvements sociaux, j'analyse un corpus de 24 entretiens effectués auprès d'activistes travaillant dans des associations de femmes au Québec afin d'observer comment elles comprennent et conceptualisent les différences ethniques et raciales et comment cela influence en retour leurs stratégies d'inclusion. Je constate que la façon dont les activistes conceptualisent l'interconnexion des rapports de genre et de race/ethnicité en tant qu'axes d'oppression des femmes a un impact sur les plateformes politiques des organisations, sur les stratégies qu'elles mettent de l'avant pour favoriser l'inclusion et l'intégration des femmes immigrantes et racisées et sur leur capacité à travailler en coalition.

Les perceptions de la sexualité et les relations de couple de femmes haïtiennes immigrantes au Québec : pour une exploration des rapports hommes femmes en Haïti

Ce mémoire a étudié les perceptions de femmes haïtiennes vivant au Québec depuis moins de cinq ans de leurs relations sexuelles avec les hommes et de leurs rapports de couple. Après avoir opté pour une méthodologie de recherche qualitative, la théorie féministe intersectionnelle a été retenue comme cadre d’analyse. Des entretiens individuels semi-dirigés ont été menés auprès de 9 femmes haïtiennes, âgées de 18 à 60 ans et ayant immigré au Québec depuis moins de cinq ans. Les perceptions des femmes de la sexualité ont été appréhendées comme étant un ensemble de discours et de pratiques inter reliés, qui se construit dès l’enfance, et qui reproduit les types de rapports inégalitaires entre hommes et femmes qui existent dans la société haïtienne et dans leur couple. Ces rapports inégalitaires sont véhiculés entre les générations à travers la plupart des institutions sociales comme la famille, l’école, la culture, la législation. Ce processus de construction des perceptions de la sexualité est également influencé par des enjeux socio-économiques et de pouvoir. Les résultats de cette recherche permettent de disposer de données scientifiques sur la sexualité des femmes et les rapports de couple en Haïti et l’influence du processus migratoire. Ces résultats soulignent également la nécessité pour le travail social haïtien d’encourager le développement de l’empowerment économique des femmes et leur participation aux débats actuels de la société sur l’évolution de la condition féminine.

Écologie politique de l'écotourisme dans les aires protégées des pays du Sud : le cas de Chi Phat dans les Cardamomes au Cambodge

L'écotourisme est souvent perçu comme une panacée capable de concilier le développement économique, la protection de l'environnement et le bien-être des communautés autour des aires protégées des pays en développement. La réalité sur le terrain est cependant tout autre, car son caractère complexe, politique et transcalaire est trop souvent négligé lors de la mise en œuvre des interventions. Le but de ce projet de recherche est de jeter un nouvel éclairage sur le développement de l'écotourisme dans les aires protégées des pays du Sud à travers une analyse critique des pratiques et des discours qui lui sont associés. Adoptant un cadre conceptuel dérivé de l'écologie politique, nous avons cherché à comprendre comment l'écotourisme affecte l'accès aux ressources naturelles pour différents acteurs sociaux. L'approche méthodologique s'appuie sur une étude de cas essentiellement qualitative qui s'attarde à un projet spécifique amorcé à Chi Phat, dans une forêt protégée des Cardamomes, au sud-ouest du Cambodge. Elle fait appel à l'analyse documentaire et discursive, à l'observation participante ainsi qu'à plus de 80 entretiens semi-directifs auprès d'acteurs clés. Nos résultats montrent d'abord qu'en matière d'écotourisme au Cambodge, il y a absence de lignes directrices claires et on observe très peu de collaboration, et ce, à tous les niveaux. Cela n'est pas étranger au fait que le gouvernement actuel accorde en général la priorité au développement devant la conservation. Ensuite, le projet d'écotourisme permet à Wildlife Alliance de justifier le maintien de la forêt protégée. Cette ONG se démarque par ailleurs des autres organisations au pays par son approche plus musclée. Le pouvoir dont elle jouit et les résultats qu'elle obtient sur le terrain tiennent en sa capacité à mobiliser, en temps opportun, l'ensemble des moyens disponibles pour contrôler l'accès. Globalement, nous pouvons affirmer que les principaux acteurs qui voient leur accès aux ressources naturelles touché négativement sont les paysans. Finalement, nous proposons deux ajouts au cadre conceptuel, soit la considération de l'aspect géographique de l'exclusion et l'introduction de modalités d'exclusion, qui permettent à notre avis une analyse plus juste de la situation.

La culture comme ressource : des groupes musicaux populaires au sein du processus de réaménagement urbain à Rio de Janeiro

Ce projet de maîtrise porte sur l’interaction entre les acteurs locaux liés à la musique populaire et l’administration publique dans le cadre du projet public-privé de réaménagement du port de Rio de Janeiro intitulé Porto Maravilha. Le travail de recherche s’est axé sur l’idée que cette interaction serait essentiellement fondée sur la façon dont la “culture” est comprise et utilisée comme ressource capable d’ajouter de la valeur à l’espace urbain, différencier les groupes entre eux et apporter une sustentation au processus d’autonomisation et de légitimation des acteurs. De nouveaux paradigmes urbanistiques, tel celui de “ville créative” (Landry, 2005), proposent d’intégrer la culture locale dans l’élaboration et l’exécution des projets avec la participation d’artistes qui sont perçus comme une source de créativité fondamentale pour rendre la ville plus compétitive dans un monde devenu de plus en plus urbain. Dans cette veine, le projet Porto Maravilha s’inspire franchement des cas de succès de rénovation urbaine créative, stimulant la culture locale et idéalisant le port de Rio comme une “nouvelle carte postale du Brésil”. En partant de la constatation que les acteurs sociaux locaux identifient le potentiel de leurs activités culturelles comme une ressource importante dans ce contexte, nous analysons tout autant les stratégies et les discours élaborés que les ressources dont ils disposent afin d’affirmer leur agentivité. Au-delà de l’action intentionnelle, nous effectuons également des analyses de leurs pratiques culturelles au quotidien en recherchant les éléments qui les constituent. Nous questionnons, par ailleurs, la manière avec laquelle les administrateurs du projet comprennent ces activités musicales et comment ils gèrent les demandes sociales et les contributions créatives de ces groupes.

L’évolution des représentations sur les langues d’élèves plurilingues du 3e cycle du primaire lors de l’implantation d’un projet d’Éveil aux langues

La présente recherche documente l’évolution des représentations sur les langues de cinq cas d’élèves plurilingues et immigrants ou issus de l’immigration, scolarisés en fin de cycle du primaire en milieu pluriethnique à Montréal, tout au long de l’implantation d’un projet d’Éveil aux langues, sur une période de deux ans. La méthodologie adoptée permet de décrire en profondeur et de façon nuancée, l’évolution des représentations des élèves sur les langues de leur répertoire plurilingue d’une part, et plus largement, sur les langues et de la diversité linguistique d’autre part. Les résultats de la recherche ont permis de mettre en évidence que l’implantation d’un projet d’Éveil aux langues sur deux ans : 1) a des effets positifs sur les représentations sur la diversité linguistique de ces élèves; 2) permet de soutenir le développement de représentations positives sur les langues du répertoire linguistique des élèves qui passe par l’acceptation de compétences partielles dans l’une ou l’autre des langues de leur répertoire et par l’expression d’un sentiment de fierté à propos de leur répertoire plurilingue; 3) permet le développement, chez les élèves, de diverses stratégies pour légitimer l’intégration de langues dans lesquelles ils ont des compétences partielles au sein de leur répertoire linguistique : apporter un jugement de valeur sur leurs compétences, spécifier leur domaine de compétence (expression orale ou écrite, compréhension orale ou écrite), qualifier, étiqueter leurs langues (langue maternelle, langue d’origine, langue seconde), adapter les définitions formelles présentées dans le projet sur le plurilinguisme à leur situation; 4) les représentations sur les langues par les élèves peuvent être marquées par le poids des représentations sociales; toutefois, cette tendance se lénifie au fur et à mesure de l’implantation du projet et une majorité d’élèves partage des représentations plus individualisées et moins marquées par des stéréotypes en fin de projet; 5) permet, pour les élèves de niveau scolaire fort et moyen, le développement d’un vocabulaire de haut niveau ainsi que le développement d’une curiosité envers la langue de l’Autre; 6) permet, pour les élèves de niveau scolaire faible, et à partir de la seconde année d’implantation, le développement d’un engagement dans les activités qui passe par une participation accrue au projet et le développement de compétence langagière (meilleure qualité argumentative); 7) offre la possibilité aux élèves de se connaître les uns les autres, d’être à l’écoute de l’Autre et d’exprimer de la curiosité envers la langue de l’autre et de reconnaître l’expertise de l’Autre, ceci participant à la mise en place d’une dynamique relationnelle propice aux apprentissages

L'œuvre d'art dans l'école au Québec : similitudes entre l'enfant et l'œuvre dans l'aperception de l'adulte

Des quelques 850 œuvres acquises par les écoles primaires et secondaires du Québec depuis les années 1980, en vertu de la Politique d’intégration des arts à l’architecture, il semble que peu d’entre elles s’adressent aux publics, enfant et adulte, qui les côtoient. La compréhension des enfants n’est pas toujours prise en compte dans le choix des œuvres commandées par un comité adulte. De même, lorsque les jeunes les rencontrent, leur sentiment spontané peut être refoulé par l’interprétation qu’en fait l’autorité – éducateur, surveillant ou parent – au profit d’un sens induit par la culture d’une société de droit. On remarque alors que le regard de l’enfant qui le pousse vers l’œuvre pour en parfaire la connaissance par l’expérience de ses sens – vision, toucher, audition, spatialité – est discrédité par celui de l’adulte qui a pour mission d'instruire et de socialiser l’élève en l’amenant à adopter un certain civisme. Comparant la volonté institutionnelle inscrite dans les textes législatifs et les rapports des comités d’intégration des œuvres à l’architecture, en amont, et les comportements et discours des enfants et adultes autour des œuvres, en aval, l’aperception des enfants dans le système scolaire peut être mise en adéquation avec l’aperception des œuvres intégrées aux écoles. L’enfant et l’œuvre dans l’institution sont-ils considérés pour eux-mêmes ou ne sont-ils vus par l’adulte qu’à travers une projection idéelle de ce qu’ils doivent être? Ainsi sera étudiée, théoriquement et empiriquement, la place laissée à l’enfant comme à l’œuvre dans l’espace scolaire afin de déterminer l’autonomie de chacun dans la relation avec l’adulte. Les théories de l’expérience matérielle, le pragmatisme deweyen et le socioconstructivisme vygotskien permettront de mettre en doute le constructivisme, le behaviorisme et le prétendu socioconstructivisme mis en œuvre dans l’institution. Par le biais de l’étude, il est compris que l’œuvre est synonyme de la place de l’enfant dans l’espace scolaire. L’adulte réserve à l’enfant, tout comme à l’œuvre, une place légitimant la sienne. À l’inverse, l’enfant intègre l’espace à sa représentation sans discrimination innée de genre, d’espèce ou de forme, comprenant l’œuvre comme lui-même.

Vers une autre temporalité de la "parthénos" : entre mythe, littérature et disciplines du corps

Cette thèse trace la généalogie culturelle de la jeune fille en Occident en ciblant les moments charnières de son devenir femme au sein de structures de savoir qui ont activement participé à forger cette figure hétéronormative. Mon objectif est de produire une analyse culturelle en forgeant une cartographie des adolescences au féminin. Afin de sortir de la temporalité téléologique de la virginité et de la défloration, j’emprunte un mot étranger, parthénos, qui fait appel à l’idée de la jeune fille, sans nécessairement se limiter à ses connotations conventionnelles. La première partie, intitulée « La virginité, une affaire de jeunes filles », laisse place à une analyse du concept de parthénos à partir d’une lecture au carrefour de la médecine, de la loi et du mythe. Une lecture du traité hippocratique De la maladie des jeunes filles dévoile comment la défloration et la grossesse deviennent une cure érotique, une discipline du corps, qui décide du passage de la jeune fille dans une temporalité utile à la Cité. Un déplacement paradigmatique s’opère au 19e siècle dans les écrits médico-légaux, parce que l’hymen, auparavant inexistant dans la doxa hippocratique, devient le signe matériel par excellence pour examiner le statut de virginité de la fille. L’analyse de ces traités (frères Beck, Ambroise Tardieu, Paulier et Hétet) révèle la configuration de pratiques et de discours d’infantilisation des victimes de viol, et le refus des médecins légistes de reconnaître qu’une femme mariée puisse être violée. À partir d’une lecture contemporaine des tragédies L’Orestie d’Eschyle et Antigone de Sophocle, je montre que les figures d’Antigone et d’Électre constituent des exemples et des symboles convaincants de ce destin funeste de la parthénos qui n’accède jamais au statut de femme mariée. À ces figures mortelles, se télescopent les figures d’Artémis et des Érinyes pour montrer le potentiel de régénération inhérent à la figure de la parthénos. La deuxième partie, qui porte le titre « Le liminaire. Repenser les devenirs de l’adolescence », engage une réflexion à la lisière du contexte contemporain des Girlhood Studies, de la psychanalyse sociale et des études féministes sur le corps et le sexe, pour faciliter le déploiement d’une cartographie plus contextualisée du concept de parthénos. Je montre ici les écueils et les effets du danger qu’engendre la rationalité économique (cf. Henry A. Giroux) pour les espaces de liberté et d’exploration propres à l’adolescence. Cette posture est appuyée sur une lecture des récentes études en psychanalyse sociale (Anne Bourgain, Olivier Douville et Edmond Ortigues). Il est ainsi question d’identifier ce qui marque le passage entre l’adolescence et l’âge adulte : la crainte de la disparition et le fantasme de la naissance de soi. La théorie de la volatilité corporelle qu’élabore Elizabeth Grosz à propos de la sexualité féminine, ainsi que les théories de Michel Foucault, reprises par Judith Butler, en ce qui concerne les disciplines du corps, répondent à mon objectif de sortir de l’écueil d’une temporalité téléologique pour saisir les effets et les ramifications du discours sur la matérialité du corps de la jeune fille, sur ce qui lui arrive lorsqu’elle ne correspond pas tout à fait à l’idéal de régulation. Enfin, la dernière partie, qui porte le titre « Temporalités de la parthénos en tant que sujet liminaire », est traversée par les modalités particulières de la parthénia qui semble désincarnée dans la littérature contemporaine. L’objectif est de prouver que la virginité est toujours un marqueur symbolique qui déploie le destin de la fille dans un horizon particulier, trop souvent celui de la disparition. En proposant un éventail de cinq textes littéraires que j’inscris au sein d’une posture généalogique, je souhaite voir dans la littérature contemporaine, une volonté, parfois aussi un échec, dans cette pensée de la parthénos en tant que sujet liminaire. Le récit Vu du ciel de Christine Angot montre que l’ascension vers le statut d’ange concerne seulement les victimes enfants. Le récit d’Angot met donc en lumière la distinction entre la vraie victime, toujours innocente et pré-pubère, et la fausse victime, l’adolescente. Contrairement à Vu du ciel, The Lovely Bones d’Alice Sebold met en scène la possibilité d’une communauté politique de filles qui sera en fait limitée par le refus du potentiel lesbien. La question du viol sera ici centrale et sera abordée à partir de l’insistance sur la voix de la narratrice Susan. La littérature devient un espace propice à la survie de la jeune fille, puisqu’elle admet la reprise de l’expérience de la première relation sexuelle. Si la communauté est convoquée dans The Lovely Bones, elle est associée à l’image de l’identité sororale dans le roman Virgin Suicides de Jeffrey Eugenides. La pathologie virale et la beauté virginale que construit le narrateur polyphonique et anonyme font exister le discours médical sur la maladie des vierges dans un contexte contemporain. Le récit médical rejoint alors le récit érotique puisque le narrateur devient médecin, détective et voyeur. À la différence de ces trois récits, Drames de princesses d’Elfriede Jelinek montre une parthénos, Blanche Neige, qui fait face à son agresseur pour s’inscrire dans une historicité discursive. Cette collision dialogique ranime le cycle tragique (celui d’une Antigone confrontant Créon) et traduit de nouveau le danger d’une superstructure sociétale composée d’images et de discours où la fille est construite comme un accessoire pour le plaisir éphémère de l’homme. À l’inverse de l’image de la vierge sacrée et désincarnée que proposent les récits d’Angot, de Sebold, d’Eugenides et de Jelinek, Virginie Despentes offre une autre réflexion dans Apocalypse bébé. Le personnage de Valentine est configuré comme une sœur des parthénoi qui préfère le suicide et la terreur à la domestication, faisant ainsi appel à une temporalité radicale et inachevable, celle de la fin de la jeune fille. Mon souhait est enfin de souligner la nécessité de penser au mérite autant épistémologique, intime que politique, d’explorer le temps des éclosions sexuelles de la fille par delà l’idée de la première relation sexuelle.

New Standards of Justice: Uncovering Motivations for Mexico’s Recent Judicial Reforms amid a Security Crisis

From the introduction: Mexico is in a state of siege. In recent years, organized crime and drug-related violence have escalated dramatically, taking innocent lives and leaving the country mired in bloodshed. The Mexican government, under the leadership of President Felipe Calderón, has responded in part by significantly extending the reach of its security operations, deploying thousands of federal police officers and military troops to combat the activities of drug cartels, and collaborating with the United States on an extensive regional security plan known as the Mérida Initiative. In the midst of the security crisis, however, the government has somewhat paradoxically adopted judicial reforms that protect human rights and civil liberties rather than erode them, specifically the presumption of innocence standard in criminal proceedings and the implementation of oral trials. Assuming that the new laws on the books will be applied in practice, these reforms represent an important commitment on the part of the government to uphold human rights and civil liberties. This is in stark contrast to the infamous judicial reforms in Colombia—the institutionalization of anonymous or “faceless” prosecutions in special courts—implemented after a surge in leftist and cartel brutality, and the murders of several prominent public and judicial officials in the 1980s.

Restarting automata with restricted utilization of auxiliary symbols

The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

The Degree of Word-Expansion of Lexicalized RRWW-Automata

Restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. We study a measure for the degree of nondeterminism of (context-free) languages in terms of deterministic restarting automata that are (strongly) lexicalized. This measure is based on the number of auxiliary symbols (categories) used for recognizing a language as the projection of its characteristic language onto its input alphabet. This type of recognition is typical for analysis by reduction, a method used in linguistics for the creation and verification of formal descriptions of natural languages. Our main results establish a hierarchy of classes of context-free languages and two hierarchies of classes of non-context-free languages that are based on the expansion factor of a language.

Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.

On CD-systems of stateless deterministic R-automata with window size one

We study cooperating distributed systems (CD-systems) of restarting automata that are very restricted: they are deterministic, they cannot rewrite, but only delete symbols, they restart immediately after performing a delete operation, they are stateless, and they have a read/write window of size 1 only, that is, these are stateless deterministic R(1)-automata. We study the expressive power of these systems by relating the class of languages that they accept by mode =1 computations to other well-studied language classes, showing in particular that this class only contains semi-linear languages, and that it includes all rational trace languages. In addition, we investigate the closure and non-closure properties of this class of languages and some of its algorithmic properties.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.