In this paper we analyze how many shuffles are necessary to get close to ran- domness for a deck of n cards. Aldous (1983) shows that approximately 8.55 (n=52) shuffles are necessary when n is large. Bayer and Diaconis (1992) use the variation distance as a measure of randomness to analyze the most commonly used method of shuffling cards, and claim that 7 shuffles are enough when n=52. We provide another idea to measure the distance from randomness for repeated shuffles. The proposed method consists of a goodness of fit test and a simple simulation. Simulation results show that we have a similar conclusion to that of Bayer and Diaconis.

Under sista året på musikhögskolan har jag arbetat på min musikaliska koordination. Det handlar om konsten att kunna spela gitarr och sjunga samtidigt. Bakgrunden till arbetet är att jag har upplevt en brist på information i ämnet, och att detta är ett koncept som fler borde sätta sig in i. Syftet med arbetet är att utforska de utmaningar och lärdomar som kommer av att spela och sjunga samtidigt.  I mitt arbete så jobbar jag med tre olika tillvägagångssätt för tre olika låtar. De tre koncepten är att spela rakt och shuffle samtidigt, flytande rytmik, och rytmisk komplexitet. I genomförande-delen så analyserar jag förhållandet mellan sång och gitarrspelet i de tre låtarna. Det gör jag genom att skriva noter till dessa, och därefter studera musiken.  Efter att ha lärt mig de tre låtarna så finns det fortfarande mycket kvar att slipa på. Med det sagt så lyckades jag musicera fram en idé som jag upplever att jag inte har hört någon gitarrist göra på en sådan hög nivå. Det jag har fått med mig från arbetet är en starkare rytmisk självständighet, en bättre förståelse för rytmernas relation till varandra, och en bättre koordinationsförmåga.

Generating unbiased permutations at run time has traditionally been accomplished through application specific optimized combinational logic and has been limited to very small permutations. For generating unbiased permutations of any larger size, variations of the memory dependent Fisher-Yates algorithm are known to be an optimal solution in software and have been relied on as a hardware solution even to this day. However, in hardware, this thesis proves Fisher-Yates to be a suboptimal solution. This thesis will show variations of Fisher-Yates to be suboptimal by proposing an alternate method that does not rely on memory and outperforms Fisher-Yates based permutation generators, while still able to scale to very large sized permutations. This thesis also proves that this proposed method is unbiased and requires a minimal input. Lastly, this thesis demonstrates a means to scale the proposed method to any sized permutations and also to produce optimal partial permutations. / Master of Science / In computing, some applications need the ability to shuffle or rearrange items based on run time information during their normal operations. A similar task is a partial shuffle where only an information dependent selection of the total items is returned in a shuffled order. Initially, there may be the assumption that these are trivial tasks. However, the applications that rely on this ability are typically related to security which requires repeatable, unbiased operations. These requirements quickly turn seemingly simple tasks to complex. Worse, often they are done incorrectly and only appear to meet these requirements, which has disastrous implications for security. A current and dominating method to shuffle items that meets these requirements was developed over fifty years ago and is based on an even older algorithm refer to as Fisher-Yates, after its original authors. Fisher-Yates based methods shuffle items in memory, which is seen as advantageous in software but only serves as a disadvantage in hardware since memory access is significantly slower than other operations. Additionally, when performing a partial shuffle, Fisher-Yates methods require the same resources as when performing a complete shuffle. This is due to the fact that, with Fisher-Yates methods, each element in a shuffle is dependent on all of the other elements. Alternate methods to meet these requirements are known but are only able to shuffle a very small number of items before they become too slow for practical use. To combat the disadvantages current methods of shuffling possess, this thesis proposes an alternate approach to performing shuffles. This alternate approach meets the previously stated requirements while outperforming current methods. This alternate approach is also able to be extended to shuffling any number of items while maintaining a useable level of performance. Further, unlike current popular shuffling methods, the proposed method has no inter-item dependency and thus offers great advantages over current popular methods with partial shuffles.

Dans ce travail, nous nous intéressons aux problèmes relatifs aux polylogarithmes et aux sommes harmoniques pris en les multiindices négatifs(au sens large, appelés dans la suite non-positifs) et en les indices mixtes. Notre étude donnera des résultats généraux sur ces objets en relation avec les algèbres de Hopf. Les techniques utilisées sont basées sur la combinatoire des séries formelles non commutatives, formes linéaires sur l’algèbre de Hopf de φ−Shuffle. Notre travail donnera aussi un processus global pour renormaliser les polyzetâs divergents. Enfin, nous appliquerons les structures mises en évidence aux systèmes dynamiques non linéaires avec entrées singulières. / In this memoir are studied the polylogarithms and the harmonic sums at non-positive (i.e. weakly negative) multi-indices. General results about these objects in relation with Hopf algebras are provided. The technics exploited here are based on the combinatorics of non commmutative generating series relative to the Hopf φ−Shuffle algebra. Our work will also propose a global process to renormalize divergent polyzetas. Finally, we will apply these ideas to non-linear dynamical systems with singular inputs.

Our research is in the general area of String Algorithms and Combinatorics on Words. Specifically, we study a generalization of square-free strings, shuffle properties of strings, and formalizing the reasoning about finite strings. The existence of infinitely long square-free strings (strings with no adjacent repeating word blocks) over a three (or more) letter finite set (referred to as Alphabet) is a well-established result. A natural generalization of this problem is that only subsets of the alphabet with predefined cardinality are available, while selecting symbols of the square-free string. This problem has been studied by several authors, and the lowest possible bound on the cardinality of the subset given is four. The problem remains open for subset size three and we investigate this question. We show that square-free strings exist in several specialized cases of the problem and propose approaches to solve the problem, ranging from patterns in strings to Proof Complexity. We also study the shuffle property (analogous to shuffling a deck of cards labeled with symbols) of strings, and explore the relationship between string shuffle and graphs, and show that large classes of graphs can be represented with special type of strings. Finally, we propose a theory of strings, that formalizes the reasoning about finite strings. By engaging in this line of research, we hope to bring the richness of the advanced field of Proof Complexity to Stringology. / Thesis / Doctor of Philosophy (PhD)

Nous introduisons les notions de forêts préordonnées et préordonnées en tas, généralisant les constructions des forêts ordonnées et ordonnées en tas. On démontre que les algèbres des forêts préordonnées et préordonnées en tas sont des algèbres de Hopf pour le coproduit de coupes et on construit un morphisme d'algèbres de Hopf dans l'algèbre des mots tassés. Ensuite, nous définissons un autre coproduit sur les forêts préordonnées donné par la contraction d'arêtes et nous donnons une description combinatoire de morphismes définis sur des algèbres de Hopf de forêts et à valeurs dans les algèbres de Hopf de battages et de battages contractants. Par ailleurs, nous introduisons la notion d'algèbre bigreffe, généralisant les notions d'algèbres de greffes à gauche et à droite. Nous décrivons l'algèbre bigreffe libre engendrée par un générateur et nous munissons cette algèbre d'une structure d'algèbre de Hopf et d'un couplage. Nous étudions ensuite le dual de Koszul de l'operade bigreffe et nous donnons une description combinatoire de l'algèbre bigreffe dual engendrée par un générateur. A l'aide d'une méthode de réécriture, nous prouvons que l'opérade bigreffe est Koszul. Nous définissons la notion de bialgèbre bigreffe infinitésimale et nous prouvons un analogue des théorèmes de Poincaré-Birkhoff-Witt et de Cartier-Milnor-Moore pour les bialgèbres bigreffe infinitésimales connexes. Pour finir, à partir de deux opérateurs de greffes, nous construisons des algèbres de Hopf d'arbres enracinés et ordonnés $ mathbf{B}^{i} $, $ i in mathbb{N}^{ast} $, $ mathbf{B}^{infty} $ et $ mathbf{B} $ vérifiant les relations d'inclusions $ mathbf{B}^{1} subseteq hdots mathbf{B}^{i} subseteq mathbf{B}^{i+1} subseteq hdots subseteq mathbf{B}^{infty} subseteq mathbf{B} $. On munit $ mathbf{B} $ d'une structure de bialgèbre dupliciale dendriforme et on en déduit que $ mathbf{B} $ est colibre et auto-duale. Nous démontrons que $ mathbf{B} $ est engendrée comme algèbre bigreffe par un générateur. / We introduce the notions of preordered and heap-preordered forests, generalizing the construction of ordered and heap-ordered forests. We prove that the algebras of preordered and heap-preordered forests are Hopf for the cut coproduct, and we construct a Hopf morphism to the Hopf algebra of packed words. In addition, we define another coproduct on the preordered forests given by the contraction of edges, and we give a combinatorial description of morphims defined on Hopf algebras of forests with values in the Hopf algebras of shuffes or quasi-shuffles. Moreover, we introduce the notion of bigraft algebra, generalizing the notions of left and right graft algebras. We describe the free bigraft algebra generated by one generator and we endow this algebra with a Hopf algebra structure, and a pairing. Next, we study the Koszul dual of the bigraft operad and we give a combinatorial description of the free dual bigraft algebra generated by one generator. With the help of a rewriting method, we prove that the bigraft operad is Koszul. We define the notion of infinitesimal bigraft bialgebra and we prove an analogue of Poincaré-Birkhoff-Witt and Cartier-Milnor-Moore theorems for connected infinitesimal bigraft bialgebras. Finally, with two grafting operators, we construct Hopf algebras of rooted and ordered trees $ mathbf{B}^{i} $, $ i in mathbb{N}^{ast} $, $ mathbf{B}^{infty} $ and $ mathbf{B} $ satisfying the inclusion relations $ mathbf{B}^{1} subseteq hdots mathbf{B}^{i} subseteq mathbf{B}^{i+1} subseteq hdots subseteq mathbf{B}^{infty} subseteq mathbf{B} $. We endow $ mathbf{B} $ with a structure of duplicial dendriform bialgebra and we deduce that $ mathbf{B} $ is cofree and self-dual. We prove that $ mathbf{B} $ is generated as bigraft algebra by one generator.

The need for redesigning existing business processes to improve their efficiency makes it essential to adequately represent, study, and automate them. The WFMC defines "workflow" as computerized facilitation or automation of a business process in whole or part. It is actually a representation of the given process, which is made up of well-defined collection of activities called tasks. Modeling and specification of a workflow involves the following steps: 1) Provide formalism for modeling and specification of workflow 2) specify the tasks together with the associated information and 3) enter the applicable business rules in form of inter-task dependencies. Earlier attempts at modeling of workflows are based on a centralized control approach, has limited applicability for modeling and control of real life workflow due to computational complexity. In this thesis, a distributed supervisory control approach is described and shown to be computationally tractable. The application of such an approach is demonstrated with a case study.

The work presented in this thesis discusses various formal language formalisms that extend classical formalisms like regular expressions and context-free grammars with additional abilities, most relating to order. This is done while focusing on the impact these extensions have on the efficiency of parsing the languages generated. That is, rather than taking a step up on the Chomsky hierarchy to the context-sensitive languages, which makes parsing very difficult, a smaller step is taken, adding some mechanisms which permit interesting spatial (in)dependencies to be modeled. The most immediate example is shuffle formalisms, where existing language formalisms are extended by introducing operators which generate arbitrary interleavings of argument languages. For example, introducing a shuffle operator to the regular expressions does not make it possible to recognize context-free languages like anbn, but it does capture some non-context-free languages like the language of all strings containing the same number of as, bs and cs. The impact these additions have on parsing has many facets. Other than shuffle operators we also consider formalisms enforcing repeating substrings, formalisms moving substrings around, and formalisms that restrict which substrings may be concatenated. The formalisms studied here all have a number of properties in common. They are closely related to existing regular and context-free formalisms. They operate in a step-wise fashion, deriving strings by sequences of rule applications of individually limited power. Each step generates a constant number of symbols and does not modify parts that have already been generated. That is, strings are built in an additive fashion that does not explode in size (in contrast to e.g. Lindenmayer systems). All languages here will have a semi-linear Parikh image. They feature some interesting characteristic involving order or other spatial constraints. In the example of the shuffle multiple derivations are in a sense interspersed in a way that each is unaware of. All of the formalisms are intended to be limited enough to make an efficient parsing algorithm at least for some cases a reasonable goal. This thesis will give intuitive explanations of a number of formalisms fulfilling these requirements, and will sketch some results relating to the parsing problem for them. This should all be viewed as preparation for the more complete results and explanations featured in the papers given in the appendices. / Denna avhandling diskuterar utökningar av klassiska formalismer inom formella språk, till exempel reguljära uttryck och kontextfria grammatiker. Utökningarna handlar på ett eller annat sätt omordning, och ett särskilt fokus ligger på att göra utökningarna på ett sätt som dels har intressanta spatiala/ordningsrelaterade effekter och som dels bevarar den effektiva parsningen som är möjlig för de ursprungliga klassiska formalismerna. Detta står i kontrast till att ta det större steget upp i Chomsky-hierarkin till de kontextkänsliga språken, vilket medför ett svårt parsningsproblem. Ett omedelbart exempel på en sådan utökning är s.k. shuffle-formalismer. Dessa utökar existerande formalismer genom att introducera operatorer som godtyckligt sammanflätar strängar från argumentspråk. Om shuffle-operator introduceras till de reguljära uttrycken ger det inte förmågan att känna igen t.ex. det kontextfria språket anbn, men det fångar istället vissa språk som inte är kontextfria, till exempel språket som består av alla strängar som innehåller lika många a:n, b:n och c:n. Sättet på vilket dessa utökningar påverkar parsningsproblemet är mångfacetterat. Utöver dessa shuffle-operatorer tas också formalismer där delsträngar kan upprepas, formalismer där delsträngar flyttas runt, och formalismer som begränsar hur delsträngar får konkateneras upp. Formalismerna som tas upp här har dock vissa egenskaper gemensamma. De är nära besläktade med de klassiska reguljära och kontextfria formalismerna. De arbetar stegvis, och konstruerar strängar genom successiva applikationer av individuellt enkla regler. Varje steg genererar ett konstant antal symboler och modifierar inte det som redan genererats. Det vill säga, strängar byggs additivt och längden på dem kan inte explodera (i kontrast till t.ex. Lindenmayer-system). Alla språk som tas upp kommer att ha en semi-linjär Parikh-avbildning. De har någon instressant spatial/ordningsrelaterad egenskap. Exempelvis sättet på vilket shuffle-operatorer sammanflätar annars oberoende deriveringar. Alla formalismerna är tänkta att vara begränsade nog att det är resonabelt att ha effektiv parsning som mål. Denna avhandling kommer att ge intuitiva förklaring av ett antal formalismer som uppfyller ovanstående krav, och kommer att skissa en blandning av resultat relaterade till parsningsproblemet för dem. Detta bör ses som förberedande inför läsning av de mer djupgående och komplexa resultaten och förklaringarna i de artiklar som finns inkluderade som appendix.

The work presented in this thesis discusses various formalisms for representing the addition of order-controlling and order-relaxing mechanisms to existing formal language models. An immediate example is shuffle expressions, which can represent not only all regular languages (a regular expression is a shuffle expression), but also features additional operations that generate arbitrary interleavings of its argument strings. This defines a language class which, on the one hand, does not contain all context-free languages, but, on the other hand contains an infinite number of languages that are not context-free. Shuffle expressions are, however, not themselves the main interest of this thesis. Instead we consider several formalisms that share many of their properties, where some are direct generalisations of shuffle expressions, while others feature very different methods of controlling order. Notably all formalisms that are studied here have a semi-linear Parikh image, are structured so that each derivation step generates at most a constant number of symbols (as opposed to the parallel derivations in for example Lindenmayer systems), feature interesting ordering characteristics, created either by derivation steps that may generate symbols in multiple places at once, or by multiple generating processes that produce output independently in an interleaved fashion, and are all limited enough to make the question of efficient parsing an interesting and reasonable goal. This vague description already hints towards the formalisms considered; the different classes of mildly context-sensitive devices and concurrent finite-state automata. This thesis will first explain and discuss these formalisms, and will then primarily focus on the associated membership problem (or parsing problem). Several parsing results are discussed here, and the papers in the appendix give a more complete picture of these problems and some related ones.

La combinatoire a permis de résoudre certains problèmes en Mathématiques, en Physique et en Informatique, en retour celles-ci inspirent des questions nouvelles à la combinatoire. Ce mémoire de thèse intitulé "Combinatoire et algorithme des factorisations tangentes à l'identité" regroupe plusieurs travaux sur la combinatoire des déformations du produit de Shuffle. L'objectif de cette thèse est d'écrire des factorisations dont le terme principal est l'identité à travers l'utilisation d'outils portant principalement sur la combinatoire des mots (ordres, graduation etc.). Dans le cas classique, soit F une algèbre libre. En raison du fait que F est une algèbre enveloppante, on a une factorisation exacte de l'identité de End(F) = F*⨶F comme un produit infini d'exponentielles (End(F) étant muni du produit de Shuffle sur la gauche et de la concaténation sur la droite, une représentation fidèle du produit de convolution). La procédure est la suivante : premièrement on commence avec une base de Poincaré-Birkhoff-Witt, deuxièmement on calcule la famille des formes coordonnées et alors les propriétés (combinatoires) non triviales de ces familles en dualité donne la factorisation. Si on part de l'autre côté, l'écriture pour le même produit ne donne exactement l'identité que sous des conditions très restrictives que nous précisons ici. Dans de nombreux autres cas (déformés), la construction explicite des paires de bases en dualité nécessite une étude combinatoire et algorithmique que nous fournissons dans ce mémoire. / Combinatorics has solved many problems in Mathematics, Physics and Computer Science, in return these domains inspire new questions to combinatorics. This memoir entitled "Combinatorics and algorithmics of factorization tangent to indentity includes several works on the combinatorial deformations of the shuffle product. The aim of this thesis is to write factorizations wich principal term is the identity through the use of tools relating mainly to combinatorics on the words (orderings, grading etc). In the classical case, let F be the free algebra. Due to the fact that F is an enveloping algebra, one has an exact factorization of the identity of End(F) = F⨶F as an infinite product of exponentials (End(F) being endowed with the shuffle product on the left and the concatenation on the right, a faithful representation of the convolution product) as follows : first on begins with a PBW basis, second one computes the family of coordinate forms and then non-trivial (combinatorial) properties of theses families in duality gives the factorization. Starting from the other side and writing the same product does give exactly identity only under very restrictive conditions that we clarify here. In many other (deformed) cases, the explicit construction of pairs of bases in duality requires combinatorial and algorithmic studies that we provide in this memoir.