Invenio v2.0: A Pythonic Framework for Large-Scale Digital Libraries

Presentation at Open Repositories 2014, Helsinki, Finland, June 9-13, 2014

Invenio v2.0: A Pythonic Framework for Large-Scale Digital Libraries

Presentation at Open Repositories 2014, Helsinki, Finland, June 9-13, 2014

Defining Contexts in Context-Free Grammars

This thesis introduces an extension of Chomsky’s context-free grammars equipped with operators for referring to left and right contexts of strings.The new model is called grammar with contexts. The semantics of these grammars are given in two equivalent ways — by language equations and by logical deduction, where a grammar is understood as a logic for the recursive definition of syntax. The motivation for grammars with contexts comes from an extensive example that completely defines the syntax and static semantics of a simple typed programming language. Grammars with contexts maintain most important practical properties of context-free grammars, including a variant of the Chomsky normal form. For grammars with one-sided contexts (that is, either left or right), there is a cubic-time tabular parsing algorithm, applicable to an arbitrary grammar. The time complexity of this algorithm can be improved to quadratic,provided that the grammar is unambiguous, that is, it only allows one parsefor every string it defines. A tabular parsing algorithm for grammars withtwo-sided contexts has fourth power time complexity. For these grammarsthere is a recognition algorithm that uses a linear amount of space. For certain subclasses of grammars with contexts there are low-degree polynomial parsing algorithms. One of them is an extension of the classical recursive descent for context-free grammars; the version for grammars with contexts still works in linear time like its prototype. Another algorithm, with time complexity varying from linear to cubic depending on the particular grammar, adapts deterministic LR parsing to the new model. If all context operators in a grammar define regular languages, then such a grammar can be transformed to an equivalent grammar without context operators at all. This allows one to represent the syntax of languages in a more succinct way by utilizing context specifications. Linear grammars with contexts turned out to be non-trivial already over a one-letter alphabet. This fact leads to some undecidability results for this family of grammars

An application of cell-cluster theory to a rare gas crystal /|n[by] K. Westera. - 260 St. Catharines [Ont.] : Dept. of Physics, Brock University,

The Lennard-Jones Devonshire 1 (LJD) single particle theory for liquids is extended and applied to the anharmonic solid in a high temperature limit. The exact free energy for the crystal is expressed as a convergent series of terms involving larger and larger sets of contiguous particles called cell-clusters. The motions of all the particles within cell-clusters are correlated to each other and lead to non-trivial integrals of orders 3, 6, 9, ... 3N. For the first time the six dimensional integral has been calculated to high accuracy using a Lennard-Jones (6-12) pair interaction between nearest neighbours only for the f.c.c. lattice. The thermodynamic properties predicted by this model agree well with experimental results for solid Xenon.

Automatic Inference of Graph Models for Complex Networks with Genetic Programming

Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.

3-O-Demethylation of thebaine and the synthesis of a flacourtia aglycone from benzoic acid.

Two synthetic projects were embarked upon, both fraught with protecting group nuance and reaction selectivity. Transformations of the opiate skeleton remain a valuable tool for the development of new medicines. Thebaine, a biosynthetic intermediate in the expression of morphine, was converted in three steps to oripavine through two parallel modes. Through the use of protecting group manipulations, two irreversible scaffold rearrangements were avoided during aryl methyl ether bond cleavage. This chemistry constitutes a new path in manipulations of the morphinan scaffold through protective groups. A new compound family, the flacourtosides, contains an unusual cyclohexenone fragment. The newly described compounds show in preliminary tests antiviral activity against dengue and chikungunya. This aglycone was approached on three pathways, all beginning with the chemoenzymatic dihydroxylation of benzoic acid. A first attempt from a known vinyl epoxide failed to epimerize and cooperate under deprotective conditions. A second and third attempt made use of a diastereoselective dihydroxylation reaction, which was critical in reaching the correct stereochemistry and oxidation state. The methyl ester of the aglycone was prepared, constituting the first synthesis of the non-trivial natural product framework.

Self-Selective Social Choice Functions

It is not uncommon that a society facing a choice problem has also to choose the choice rule itself. In such situation voters’ preferences on alternatives induce preferences over the voting rules. Such a setting immediately gives rise to a natural question concerning consistency between these two levels of choice. If a choice rule employed to resolve the society’s original choice problem does not choose itself when it is also used in choosing the choice rule, then this phenomenon can be regarded as inconsistency of this choice rule as it rejects itself according to its own rationale. Koray (2000) proved that the only neutral, unanimous universally self-selective social choice functions are the dictatorial ones. Here we in troduce to our society a constitution, which rules out inefficient social choice rules. When inefficient social choice rules become unavailable for comparison, the property of self-selectivity becomes weaker and we show that some non-trivial self-selective social choice functions do exist. Under certain assumptions on the constitution we describe all of them.

Teaching ethics to employees of a state public utilities company in a developing country: A case study

Cette étude de cas est issue d’un module final de formation pour les employés du service public d’une agence de l’eau. Nous explorons les résultats de plusieurs stratégies utilisées pour souligner le besoin de changement dans les comportements individuels et institutionnels en vue d’améliorer les services aux clients. En particulier, nous explorons certaines manières d’ouvrir la discussion sur les pratiques de corruption de manière non-triviale sans offenser les sensibilités ou provoquer l’indifférence. Comme point de départ, il est demandé aux participants de relever les problèmes institutionnels qu’ils caractérisent comme éthiques, même si d’autres problèmes appartiennent à d’autres catégories identifiées plus tard. Pour éviter une approche purement théorique des devoirs et obligations envers les clients, ils sont dérivés de la mission de l’agence telle que définit par la loi qui l’a créée.

Une architecture parallèle distribuée et tolérante aux pannes pour le protocole interdomaine BGP au cœur de l’Internet

L’augmentation du nombre d’usagers de l’Internet a entraîné une croissance exponentielle dans les tables de routage. Cette taille prévoit l’atteinte d’un million de préfixes dans les prochaines années. De même, les routeurs au cœur de l’Internet peuvent facilement atteindre plusieurs centaines de connexions BGP simultanées avec des routeurs voisins. Dans une architecture classique des routeurs, le protocole BGP s’exécute comme une entité unique au sein du routeur. Cette architecture comporte deux inconvénients majeurs : l’extensibilité (scalabilité) et la fiabilité. D’un côté, la scalabilité de BGP est mesurable en termes de nombre de connexions et aussi par la taille maximale de la table de routage que l’interface de contrôle puisse supporter. De l’autre côté, la fiabilité est un sujet critique dans les routeurs au cœur de l’Internet. Si l’instance BGP s’arrête, toutes les connexions seront perdues et le nouvel état de la table de routage sera propagé tout au long de l’Internet dans un délai de convergence non trivial. Malgré la haute fiabilité des routeurs au cœur de l’Internet, leur résilience aux pannes est augmentée considérablement et celle-ci est implantée dans la majorité des cas via une redondance passive qui peut limiter la scalabilité du routeur. Dans cette thèse, on traite les deux inconvénients en proposant une nouvelle approche distribuée de BGP pour augmenter sa scalabilité ainsi que sa fiabilité sans changer la sémantique du protocole. L’architecture distribuée de BGP proposée dans la première contribution est faite pour satisfaire les deux contraintes : scalabilité et fiabilité. Ceci est accompli en exploitant adéquatement le parallélisme et la distribution des modules de BGP sur plusieurs cartes de contrôle. Dans cette contribution, les fonctionnalités de BGP sont divisées selon le paradigme « maître-esclave » et le RIB (Routing Information Base) est dupliqué sur plusieurs cartes de contrôle. Dans la deuxième contribution, on traite la tolérance aux pannes dans l’architecture élaborée dans la première contribution en proposant un mécanisme qui augmente la fiabilité. De plus, nous prouvons analytiquement dans cette contribution qu’en adoptant une telle architecture distribuée, la disponibilité de BGP sera augmentée considérablement versus une architecture monolithique. Dans la troisième contribution, on propose une méthode de partitionnement de la table de routage que nous avons appelé DRTP pour diviser la table de BGP sur plusieurs cartes de contrôle. Cette contribution vise à augmenter la scalabilité de la table de routage et la parallélisation de l’algorithme de recherche (Best Match Prefix) en partitionnant la table de routage sur plusieurs nœuds physiquement distribués.

Apprentissage et changement : l’Advocacy Coalition Framework et l’évolution de la politique militaire africaine de la France 1994-2008

La politique militaire de la France en Afrique est en évolution. La véracité factuelle de ce constat est désormais difficilement contestable. Ce changement s’observe d’abord dans le discours où l’on parle de plus en plus d’anciennes pratiques dépassées et reconnaît que ce qui était politiquement possible et admis il y a vingt ans ne l’est plus aujourd’hui. Ce processus s’incarne ensuite dans la modification des instruments d’action ainsi que dans les modes et les niveaux d’utilisation de ces instruments. Partant de ces considérations, le présent travail se propose d’examiner les facteurs à l’origine de cette évolution. Il part des réponses jusqu’ici proposées pour apporter un éclairage nouveau au sujet des forces et dynamiques à la base des changements annoncés ou observés. Contrairement à la littérature existante qui a jusqu’ici privilégié les approches matérialistes et utilitaristes pour expliquer les transformations entreprises et celles promises dans la politique militaire africaine de la France, cette étude propose, à l’inverse, une perspective inspirée des approches cognitives et axée sur le processus d’apprentissage. Ainsi, plutôt que de voir dans les réformes ici analysées le résultat exclusif de changements structurels ou systémiques survenus dans l’environnement économique, social ou international des États, notre analyse fera davantage valoir que cette transformation a pour l’essentiel été une adaptation faite à la lumière des leçons tirées d’expériences antérieures. Cette analyse s’appuie sur l’Advocacy Coalition Framework. Développée par Paul A Sabatier et ses collègues, il postule que la prise de décision en matière de politique publique peut être mieux comprise comme une compétition entre coalitions de cause, chacune étant constituée d’acteurs provenant d’une multitudes d’institutions (leaders de groupes d’intérêt, agences administratives, chercheurs, journalistes) qui partagent un système de croyances lié à l’action publique et qui s’engagent dans un effort concerté afin de traduire des éléments de leur système de croyances en une politique publique.

On some Density Theorems in Number Theory and Group Theory

Gowers, dans son article sur les matrices quasi-aléatoires, étudie la question, posée par Babai et Sos, de l'existence d'une constante $c>0$ telle que tout groupe fini possède un sous-ensemble sans produit de taille supérieure ou égale a $c|G|$. En prouvant que, pour tout nombre premier $p$ assez grand, le groupe $PSL_2(\mathbb{F}_p)$ (d'ordre noté $n$) ne posséde aucun sous-ensemble sans produit de taille $c n^{8/9}$, il y répond par la négative. Nous allons considérer le probléme dans le cas des groupes compacts finis, et plus particuliérement des groupes profinis $SL_k(\mathbb{Z}_p)$ et $Sp_{2k}(\mathbb{Z}_p)$. La premiére partie de cette thése est dédiée à l'obtention de bornes inférieures et supérieures exponentielles pour la mesure suprémale des ensembles sans produit. La preuve nécessite d'établir préalablement une borne inférieure sur la dimension des représentations non-triviales des groupes finis $SL_k(\mathbb{Z}/(p^n\mathbb{Z}))$ et $Sp_{2k}(\mathbb{Z}/(p^n\mathbb{Z}))$. Notre théoréme prolonge le travail de Landazuri et Seitz, qui considérent le degré minimal des représentations pour les groupes de Chevalley sur les corps finis, tout en offrant une preuve plus simple que la leur. La seconde partie de la thése à trait à la théorie algébrique des nombres. Un polynome monogéne $f$ est un polynome unitaire irréductible à coefficients entiers qui endengre un corps de nombres monogéne. Pour un nombre premier $q$ donné, nous allons montrer, en utilisant le théoréme de densité de Tchebotariov, que la densité des nombres premiers $p$ tels que $t^q -p$ soit monogéne est supérieure ou égale à $(q-1)/q$. Nous allons également démontrer que, quand $q=3$, la densité des nombres premiers $p$ tels que $\mathbb{Q}(\sqrt[3]{p})$ soit non monogéne est supérieure ou égale à $1/9$.

Essays in political economy

Cette thése relie trois articles sur l'économie politique. Ces articles analysent à la fois théoriquement et empiriquement si, et dans quelle mesure, trois phénomènes politiques différents (les partis politiques, les guerres civiles et les menaces externes), et leur interaction, influent sur les résultats économiques. Le premier chapitre étudie l'impact de la présence au pouvoir des politiciens de nouveaux partis politiques sur la taille du gouvernement. Le chapitre se concentre sur les municipalités colombiennes, où les nouveaux partis politiques ont été nombreux et fructueux au cours des dernières années. Les estimations par régressions sur discontinuité montrent que les dépenses publiques et les recettes fiscales sont significativement plus élevées dans les municipalités gouvernées par un maire d'un nouveau parti politique. En utilisant des informations sur la politique locale et des caractéristiques des nouveaux partis, je soutiens que ce résultat peut être expliqué par le fait qu'il y a moins d'information sur les politiciens de nouveaux partis que les politiciens des partis traditionnels. Le deuxième chapitre développe une nouvelle explication de l'impact des guerres civiles et des conflits interétatiques sur le state-building qui repose sur l'idée que les protagonistes de ces deux types de conflits peuvent avoir un lien (ethnique ou idéologique). Un premier résultat montre que la force de ce lien détermine si les conflits contre des adversaires internes (i.e. guerres civiles) ou des ennemis externes (i.e. conflits interétatiques) sont complémentaires ou se substituent, conduisant à plus ou moins d'investissement en capacité fiscale. La théorie prédit également un rôle non trivial de la stabilité politique dans la relation entre les deux types de conflits et la capacité fiscale: un deuxième résultat montre que, bien que la stabilité politique se traduit par moins de capacité fiscale, plus de stabilité n'implique pas plus de state-building. Leur équivalence dépend du niveau de cohésion des institutions. Un nouveau mécanisme par lequel plus de stabilité politique peut impliquer moins de state-building est proposé. En outre, il est démontré que des corrélations dans les données cross-country sont compatibles avec la théorie. Le troisième chapitre examine la relation entre la probabilité d'occurrence d'un conflit intérieur violent et le risque qu'un tel conflit "s'externalise" (c'est à dire se propage dans un autre pays en devenant un conflit interétatique). Je considère une situation dans laquelle un conflit interne entre un gouvernement et un groupe rebelle peut s'externaliser. Je montre que le risque d'externalisation augmente la probabilité d'un accord de paix, mais seulement si le gouvernement est suffisamment puissant par rapport aux rebelles, et si le risque d'externalisation est suffisamment élevé. Je montre comment ce modèle aide à comprendre les récents pourparlers de paix entre le gouvernement colombien et le groupe le plus puissant des rebelles dans le pays, les FARC.

Practical and Foundational Aspects of Secure Computation

Il y a des problemes qui semblent impossible a resoudre sans l'utilisation d'un tiers parti honnete. Comment est-ce que deux millionnaires peuvent savoir qui est le plus riche sans dire a l'autre la valeur de ses biens ? Que peut-on faire pour prevenir les collisions de satellites quand les trajectoires sont secretes ? Comment est-ce que les chercheurs peuvent apprendre les liens entre des medicaments et des maladies sans compromettre les droits prives du patient ? Comment est-ce qu'une organisation peut ecmpecher le gouvernement d'abuser de l'information dont il dispose en sachant que l'organisation doit n'avoir aucun acces a cette information ? Le Calcul multiparti, une branche de la cryptographie, etudie comment creer des protocoles pour realiser de telles taches sans l'utilisation d'un tiers parti honnete. Les protocoles doivent etre prives, corrects, efficaces et robustes. Un protocole est prive si un adversaire n'apprend rien de plus que ce que lui donnerait un tiers parti honnete. Un protocole est correct si un joueur honnete recoit ce que lui donnerait un tiers parti honnete. Un protocole devrait bien sur etre efficace. Etre robuste correspond au fait qu'un protocole marche meme si un petit ensemble des joueurs triche. On demontre que sous l'hypothese d'un canal de diusion simultane on peut echanger la robustesse pour la validite et le fait d'etre prive contre certains ensembles d'adversaires. Le calcul multiparti a quatre outils de base : le transfert inconscient, la mise en gage, le partage de secret et le brouillage de circuit. Les protocoles du calcul multiparti peuvent etre construits avec uniquements ces outils. On peut aussi construire les protocoles a partir d'hypoth eses calculatoires. Les protocoles construits a partir de ces outils sont souples et peuvent resister aux changements technologiques et a des ameliorations algorithmiques. Nous nous demandons si l'efficacite necessite des hypotheses de calcul. Nous demontrons que ce n'est pas le cas en construisant des protocoles efficaces a partir de ces outils de base. Cette these est constitue de quatre articles rediges en collaboration avec d'autres chercheurs. Ceci constitue la partie mature de ma recherche et sont mes contributions principales au cours de cette periode de temps. Dans le premier ouvrage presente dans cette these, nous etudions la capacite de mise en gage des canaux bruites. Nous demontrons tout d'abord une limite inferieure stricte qui implique que contrairement au transfert inconscient, il n'existe aucun protocole de taux constant pour les mises en gage de bit. Nous demontrons ensuite que, en limitant la facon dont les engagements peuvent etre ouverts, nous pouvons faire mieux et meme un taux constant dans certains cas. Ceci est fait en exploitant la notion de cover-free families . Dans le second article, nous demontrons que pour certains problemes, il existe un echange entre robustesse, la validite et le prive. Il s'effectue en utilisant le partage de secret veriable, une preuve a divulgation nulle, le concept de fantomes et une technique que nous appelons les balles et les bacs. Dans notre troisieme contribution, nous demontrons qu'un grand nombre de protocoles dans la litterature basee sur des hypotheses de calcul peuvent etre instancies a partir d'une primitive appelee Transfert Inconscient Veriable, via le concept de Transfert Inconscient Generalise. Le protocole utilise le partage de secret comme outils de base. Dans la derniere publication, nous counstruisons un protocole efficace avec un nombre constant de rondes pour le calcul a deux parties. L'efficacite du protocole derive du fait qu'on remplace le coeur d'un protocole standard par une primitive qui fonctionne plus ou moins bien mais qui est tres peu couteux. On protege le protocole contre les defauts en utilisant le concept de privacy amplication .

On the design of customized risk measures in insurance, the problem of capital allocation and the theory of fluctuations for Lévy processes

Dans cette thèse, nous étudions quelques problèmes fondamentaux en mathématiques financières et actuarielles, ainsi que leurs applications. Cette thèse est constituée de trois contributions portant principalement sur la théorie de la mesure de risques, le problème de l’allocation du capital et la théorie des fluctuations. Dans le chapitre 2, nous construisons de nouvelles mesures de risque cohérentes et étudions l’allocation de capital dans le cadre de la théorie des risques collectifs. Pour ce faire, nous introduisons la famille des "mesures de risque entropique cumulatifs" (Cumulative Entropic Risk Measures). Le chapitre 3 étudie le problème du portefeuille optimal pour le Entropic Value at Risk dans le cas où les rendements sont modélisés par un processus de diffusion à sauts (Jump-Diffusion). Dans le chapitre 4, nous généralisons la notion de "statistiques naturelles de risque" (natural risk statistics) au cadre multivarié. Cette extension non-triviale produit des mesures de risque multivariées construites à partir des données financiéres et de données d’assurance. Le chapitre 5 introduit les concepts de "drawdown" et de la "vitesse d’épuisement" (speed of depletion) dans la théorie de la ruine. Nous étudions ces concepts pour des modeles de risque décrits par une famille de processus de Lévy spectrallement négatifs.

Topological order in a broken-symmetry state

À travers cette thèse, nous revisitons les différentes étapes qui ont conduit à la découverte des isolants topologiques, suite à quoi nous nous penchons sur la question à savoir si une phase topologiquement non-triviale peut coexister avec un état de symétrie brisée. Nous abordons les concepts les plus importants dans la description de ce nouvel état de la matière, et tentons de comprendre les conséquences fascinantes qui en découlent. Il s’agit d’un champ de recherche fortement alimenté par la théorie, ainsi, l’étude du cadre théorique est nécessaire pour atteindre une compréhension profonde du sujet. Le chapitre 1 comprend un retour sur l’effet de Hall quantique, afin de motiver les sections subséquentes. Le chapitre 2 présente la première réalisation d’un isolant topologique à deux dimensions dans un puits quantique de HgTe/CdTe, suite à quoi ces résultats sont généralisés à trois dimensions. Nous verrons ensuite comment incorporer des principes de topologie dans la caractérisation d’un système spécifique, à l’aide d’invariants topologiques. Le chapitre 3 introduit le premier dérivé de l’état isolant topologique, soit l’isolant topologique antiferromagnétique (ITAF). Après avoir motivé théoriquement le sujet et introduit un invariant propre à ce nouvel état ITAF, qui est couplé à l’ordre de Néel, nous explorons, dans les chapitres 4 et 5, deux candidats de choix pour la phase ITAF : GdBiPt et NdBiPt.