Tesis sobre el tema "Algebraic automata theory"

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

The specification of a decoder, i.e., a program that translates sentences from one natural language into another, is an intricate process, driven by the application and lacking a canonical methodology. The practical nature of decoder development inhibits the transfer of knowledge between theory and application, which is unfortunate because many contemporary decoders are in fact related to formal-language theory. This thesis proposes an algebraic framework where a decoder is specified by an expression built from a fixed set of operations. As yet, this framework accommodates contemporary syntax-based decoders, it spans two levels of abstraction, and, primarily, it encourages mutual stimulation between the theory of weighted tree automata and the application.

Cette thèse porte sur certaines extensions des automates pondérés, et étudie les séries qu’ils réalisent en fonction de la nature des poids.Ces extensions se distinguent par les mouvements supplémentaires autorisés à la tête de lecture de l’automate : retour au début du mot pour les automates circulaires, changement de sens de lecture pour les automates boustrophédons.Dans le cas général, les automates pondérés circulaires sont plus puissants que les automates unidirectionnels classiques, et moins puissants que les boustrophédons.On introduit de plus les expressions de Hadamard, qui sont une extension des expressions rationnelles et qui permettent de dénoter le comportement des automates circulaires. Les aspects algorithmiques de cette conversion sont étudiés dans le cas où les poids appartiennent à un semi-anneau rationnellement additif.On montre que lorsque les poids sont des nombres rationnels, réels ou complexes, les automates circulaires sont aussi expressifs que les boustrophédons.Enfin, si les poids forment un bi-monoïde localement fini, les automates boustrophédons ne sont pas plus expressifs que les automates pondérés classsiques
This thesis deals with some extensions of weighted automata,and studies the series they can realisedepending on the nature of their weigths.These extensions are characterised by howthe input head of the automaton is allowed to move:rotating automata can go back at the beginning of the word,and two-way automata can change the reading direction.In the general setting, weigthed rotating automata are morepowerful than classical one-way automata, and less powerfulthan two-way ones.Moreover, we introduce Hadamard expressions,which are an extension of rational expressions and can denotethe behaviour of rotating automata.The algorithms for this conversion are studied when the weights belong toa rationally additive semiring.Then, rotating automata are shown as expressive as two-way automatain the case of rational, real or complex numbers.It is also proved that two-way and one-way automataare equivalent when weighted on a locally finite bimonoid

L'évaluation efficace des expressions régulières constitue un défi persistant depuis de nombreuses décennies. Au fil du temps, des progrès substantiels ont été réalisés grâce à une variété d'approches, allant de nouveaux et ingénieux algorithmes à des optimisations complexes de bas niveau.Les outils de pointe de ce domaine utilisent ces techniques d'optimisation, et repoussent constamment les limites de leur efficacité. Une avancée notoire réside dans l'intégration de la vectorisation, qui exploite une forme de parallélisme de bas niveau pour traiter l'entrée par blocs, entraînant ainsi d'importantes améliorations de performances. Malgré une recherche approfondie sur la conception d'algorithmes sur mesure pour des tâches particulières, ces solutions manquent souvent de généralisabilité, car la méthodologie sous-jacente à ces algorithmes ne peut pas être appliquée de manière indiscriminée à n'importe quelle expression régulière, ce qui rend difficile son intégration dans les outils existants.Cette thèse présente un cadre théorique permettant de générer des programmes vectorisés particuliers capables d'évaluer les expressions régulières correspondant aux expressions rationnelles appartenant à une classe logique donnée. L'intérêt de ces programmes vectorisés vient de l'utilisation de la théorie algébrique des automates, qui offre certains outils algébriques permettant de traiter les lettres en parallèle. Ces outils permettent également d'analyser les langages réguliers plus finement, offrent accès à des optimisations des programmes vectorisés basées sur les propriétés algébriques de ces langages. Cette thèse apporte des contributions dans deux domaines. D'une part, nous présentons des implémentations et des benchmarks préliminaires, afin d'étudier les possibilités offertes par l'utilisation de l'algèbre et de la vectorisation dans les algorithmes d'évaluation des expressions régulières. D'autre part, nous proposons des algorithmes capables de générer des programmes vectorisés reconnaissant les langages appartenant à deux classes d'expressions rationnelles, la logique du premier ordre et sa restriction aux formules utilisant au plus deux variables
The pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables

Automated reasoning technology provides means for inference in a formal context via a multitude of disparate reasoning techniques. Combining different techniques not only increases the effectiveness of single systems but also provides a more powerful approach to solving hard problems. Consequently combined reasoning systems have been successfully employed to solve non-trivial mathematical problems in combinatorially rich domains that are intractable by traditional mathematical means. Nevertheless, the lack of domain specific knowledge often limits the effectiveness of these systems. In this thesis we investigate how the combination of diverse reasoning techniques can be employed to pre-compute additional knowledge to enable mathematical discovery in finite and potentially infinite domains that is otherwise not feasible. In particular, we demonstrate how we can exploit bespoke symbolic computations and automated theorem proving to automatically compute and evolve the structural knowledge of small size finite structures in the algebraic theory of quasigroups. This allows us to increase the solvability horizon of model generation systems to find solution models for large size finite algebraic structures previously unattainable. We also present an approach to exploring infinite models using a mixture of automated tools and user interaction to iteratively inspect the structure of solutions and refine search. A practical implementation combines a specialist term rewriting system with bespoke graph algorithms and visualization tools and has been applied to solve the generalized version of Kuratowski's classical closure-complement problem from point-set topology that had remained open for several years.

This thesis provides a specification theory with strong algebraic and compositionality properties, allowing for the systematic construction of new components out of existing ones, while ensuring that given properties continue to hold at each stage of system development. The theory shares similarities with the interface automata of de Alfaro and Henzinger, but is linear-time in the style of Dill's trace theory, and is endowed with a richer collection of operators. Components are assumed to communicate with one another by synchronisation of input and output actions, with the component specifying the allowed sequences of interactions between itself and the environment. When the environment produces an interaction that the component is unwilling to receive, a communication mismatch occurs, which can correspond to run-time error or underspecification. These are modelled uniformly as inconsistencies. A linear-time refinement preorder corresponding to substitutivity preserves the absence of inconsistency under all environments, allowing for the safe replacement of components at run-time. To build complex systems, a range of compositional operators are introduced, including parallel composition, logical conjunction and disjunction, hiding, and quotient. These can be used to examine the structural behaviour of a system, combine independently developed requirements, abstract behaviour, and incrementally synthesise missing components, respectively. It is shown that parallel composition is monotonic under refinement, conjunction and disjunction correspond to the meet and join operations on the refinement preorder, and quotient is the adjoint of parallel composition. Full abstraction results are presented for the equivalence defined as mutual refinement, a consequence of the refinement being the weakest preorder capturing substitutivity. Extensions of the specification theory with progress-sensitivity (ensuring that refinement cannot introduce quiescence) and real-time constraints on when interactions may and may not occur are also presented. These theories are further complemented by assume-guarantee frameworks for supporting component-based reasoning, where contracts (characterising sets of components) separate the assumptions placed on the environment from the guarantees provided by the components. By defining the compositional operators directly on contracts, sound and complete assume-guarantee rules are formulated that preserve both safety and progress. Examples drawn from distributed systems are used to demonstrate how these rules can be used for mechanically deriving component-based designs.

Ce mémoire est constitué de 3 parties.La NP-complétude de la satisfaction de combinaisons booléennes de contraintes de sous-arbres est démontrée dans l'article [Ven87] ; la partie I de ce mémoire étudie dans quelle mesure l'ajout de contraintes régulières laisse espérer conserver la complexité NP. Ce modèle étendu définit une nouvelle classe de langages dont l'expressivité est comparée à celle des Rigid Tree Automata [JKV11]. Puis un début de formalisation des t-dags est donné.Les patterns ont été étudiés, principalement du point de vue des contraintes sur les données qu'ils demandent. La partie II de ce mémoire les étudie plus finement, en mettant de côté les données. Les squelettes sont définis en tant qu'intermédiaire de calcul et le fait que leur syntaxe caractérise leur sémantique est démontré. Puis un lemme de pompage est donné dans un cas restreint, un autre dans le cas général est étudié et conjecturé. Ensuite des fragments de combinaisons booléennes de patterns sont comparés en expressivité pour terminer avec l'étude de la complexité des problèmes de model-checking, satisfaisabilité et DTD-satisfaisabilité sur les dits fragments.Le contenu de la partie III constitue l'article [FMS11], c'est la démonstration de la caractérisation des langages des automates fortement déterministes de niveau 2 par des systèmes d'équations récurrentes caténatives. Celle-ci utilise, entre autres, des techniques de réécriture, la notion d'inconnues non-réécrivables et les ordres noethériens. Cette caractérisation constitue le cas de base de la récurrence démontrée dans [Sén07]
This thesis is in 3 parts.The NP-completeness of satisfiability of boolean combinations of subtree constraints is shown in the article [Ven87] ; in the part I of this thesis, we study whether adding regular contraints lets hope for keeping the same complexity. This extended model defines a new class of languages which is compared in expressivity to the Rigid Tree Automata [JKV11]. Then a begining of formalisation of the t-dags is developped.The patterns have been studied mainly from the point of view of the constraints they demand on the data. The part II of this thesis study them more finely, by putting aside the data. The skeletons are defined as calculus intermediate and the characterisation holding between their syntax and their semantics is shown. Then a pumping lemma is prooved in a restreict case, another one is conjectured in the most general case. Then fragments of boolean combinations of patterns are compared in expressivity, this parts ends with the study of complexity of model-checking, satisfiability and DTD-satisfiability on these fragments.The content of part III constitutes the article [FMS11], it is the demonstration of the characterisation of strongly-deterministic 2-level pushdown automata by recurrent catenative equation systems. This proof uses in particular, some rewriting techniques, unrewritable unknowns and noetherian orders. This characterisation provides the base case of the recurrence shown in [Sén07]

We give a concise introduction to the coalgebraic theory of Moore machines, and building on [6], develop a method for constructing a final Moore machine based on a simple modal logic. Completeness for the logic follows easily from the finality construction, and we furthermore show how this logical framework can be used for machine learning.

Recent efforts to classify off-shell representations of supersymmetry without a central charge have focused upon directed, supermultiplet graphs of hypercubic topology known as Adinkras. These encodings of Super Poincare algebras, depict every generator of a chosen supersymmetry as a node-pair transformtion between fermionic / bosonic component fields. This research thesis is a culmination of investigating novel diagrammatic sums of gauge quotients by supersymmetric images of other Adinkras, and the correlated building of field theoretic worldline Lagrangians to accommodate both classical and quantum venues. We find Ref [40], that such gauge quotients do not yield other stand alone or ”proper” Adinkras as afore sighted, nor can they be decomposed into supermultiplet sums, but are rather a connected ”Adinkraic network”. Their iteration, analogous to Weyl's construction for producing all finite-dimensional unitary representations in Lie algebras, sets off chains of algebraic paradigms in discrete-graph and continuous-field variables, the links of which feature distinct, supersymmetric Lagrangian templates. Collectively, these Adiankraic series air new symbolic genera for equation to phase moments in Feynman path integrals. Guided in this light, we proceed by constructing Lagrangians actions for the N = 3 supermultiplet YI /(iDI X) for I = 1, 2, 3, where YI and X are standard, Salam-Strathdee superfields: YI fermionic and X bosonic. The system, bilinear in the component fields exhibits a total of thirteen free parameters, seven of which specify Zeeman-like coupling to external background (magnetic) fluxes. All but special subsets of this parameter space describe aperiodic oscillatory responses, some of which are found to be surprisingly controlled by the golden ratio, ? ? 1.61803, Ref [52]. It is further determined that these Lagrangians allow an N = 3 ? 4 supersymmetric extension to the Chiral-Chiral and Chiral-twisted- Chiral multiplet, while a subset admits two inequivalent such extensions. In a natural progression, a continuum of observably and usefully inequivalent, finite-dimensional off-shell representations of worldline N = 4 extended supersymmetry are explored, that are variate from one another but in the value of a tuning parameter, Ref [53]. Their dynamics turns out to be nontrivial already when restricting to just bilinear Lagrangians. In particular, we find a 34-parameter family of bilinear Lagrangians that couple two differently tuned supermultiplets to each other and to external magnetic fluxes, where the explicit parameter dependence is unremovable by any field redefinition and is therefore observable. This offers the evaluation of X-phase sensitive, off-shell path integrals with promising correlations to group product decompositions and to deriving source emergences of higher-order background flux-forms on 2-dimensional manifolds, the stacks of which comprise space-time volumes. Application to nonlinear sigma models would naturally follow, having potential use in M- and F- string theories.
Ph.D.
Doctorate
Physics
Sciences
Physics

Les algèbres de relations apparaissent naturellement dans de nombreux cadres, en informatique comme en mathématiques. Elles constituent en particulier un formalisme tout à fait adapté à la sémantique des programmes impératifs. Les algèbres de Kleene constituent un point de départ : ces algèbres jouissent de résultats de décidabilités très satisfaisants, et admettent une axiomatisation complète. L'objectif de cette thèse a été d'étendre les résultats connus sur les algèbres de Kleene à des extensions de celles-ci.Nous nous sommes tout d'abord intéressés à une extension connue : les algèbres de Kleene avec converse. La décidabilité de ces algèbres était déjà connue, mais l'algorithme prouvant ce résultat était trop compliqué pour être utilisé en pratique. Nous avons donné un algorithme plus simple, plus efficace, et dont la correction est plus facile à établir. Ceci nous a permis de placer ce problème dans la classe de complexité PSpace-complete.Nous avons ensuite étudié les allégories de Kleene. Sur cette extension, peu de résultats étaient connus. En suivant des résultats sur des algèbres proches, nous avons établi l'équivalence du problème d'égalité dans les allégories de Kleene à l'égalité de certains ensembles de graphes. Nous avons ensuite développé un modèle d'automate original (les automates de Petri), basé sur les réseaux de Petri, et avons établi l'équivalence de notre problème original avec le problème de comparaison de ces automates. Nous avons enfin développé un algorithme pour effectuer cette comparaison dans le cadre restreint des treillis de Kleene sans identité. Cet algorithme utilise un espace exponentiel. Néanmoins, nous avons pu établir que la comparaison d'automates de Petri dans ce cas est ExpSpace-complète. Enfin, nous nous sommes intéressés aux algèbres de Kleene Nominales. Nous avons réalisé que les descriptions existantes de ces algèbres n'étaient pas adaptées à la sémantique relationnelle des programmes. Nous les avons donc modifiées pour nos besoins, et ce faisant avons trouvé diverses variations naturelles de ce modèle. Nous avons donc étudié en détails et en Coq les ponts que l'on peut établir entre ces variantes, et entre le modèle “classique” et notre nouvelle version
Algebras of relations appear naturally in many contexts, in computer science as well as in mathematics. They constitute a framework well suited to the semantics of imperative programs. Kleene algebra are a starting point: these algebras enjoy very strong decidability properties, and a complete axiomatisation. The goal of this thesis was to export known results from Kleene algebra to some of its extensions. We first considered a known extension: Kleene algebras with converse. Decidability of these algebras was already known, but the algorithm witnessing this result was too complicated to be practical. We proposed a simpler algorithm, more efficient, and whose correctness is easier to establish. It allowed us to prove that this problem lies in the complexity class PSpace-complete.Then we studied Kleene allegories. Few results were known about this extension. Following results about closely related algebras, we established the equivalence between equality in Kleene allegories and equality of certain sets of graphs. We then developed an original automaton model (so-called Petri automata), based on Petri nets. We proved the equivalence between the original problem and comparing these automata. In the restricted setting of identity-free Kleene lattices, we also provided an algorithm performing this comparison. This algorithm uses exponential space. However, we proved that the problem of comparing Petri automata lies in the class ExpSpace-complete.Finally, we studied Nominal Kleene algebras. We realised that existing descriptions of these algebra were not suited to relational semantics of programming languages. We thus modified them accordingly, and doing so uncovered several natural variations of this model. We then studied formally the bridges one could build between these variations, and between the existing model and our new version of it. This study was conducted using the proof assistant Coq

Ce mémoire concerne le traitement algorithmique des représentations matricielles. Les techniques y sont illustrées sur deux exemples, les algèbres de Hecke et les automates à multiplicités. Les algèbres de Hecke interviennent dans plusieurs domaines (dont l'algèbre ou la physique statistique) qui demandent de pouvoir y calculer efficacement. Ici sont rassemblés des algorithmes implémentés en Maple constituant la bibliothèque SHRI. Par l'action d'opérateurs de symétrisation sur des Q-Vandermonde, on détermine un système complet de représentations polynomiales. En calculant les polynômes minimaux de chaque bloc de la représentation régulière, on en déduit l'inverse d'un élément s'il existe. On construit une famille complète d'idempotents minimaux orthogonaux en évaluant les gz-polynômes en les q-analogues des éléments de Jucys-Murphy. Ces polynômes sont de degré minimal en la variable d'index maximal (la plus coûteuse). On en déduit un calcul des bases de Gelfand-Zetlin des modules irréductibles. Le caractère d'un élément de l'algèbre de Hecke est, grâce à un algorithme de conjugaison, une combinaison linéaire d'évaluations sur des produits de cycles calculées efficacement par une formule de J. Desarmenien généralisant la formule de Murnaghan-Nakayama. Une forme bilinéaire invariante permet d'expliciter les idempotents centraux via la formule de Kilmoyer. Le phénomène de compression spectrale observé lors de tests sur le package réside en la compression des deux paramètres formels de l'algèbre de Hecke générique en un seul par l'implémentation des isomorphismes semi-linéaires entre les algèbres de Hecke. Les calculs dans l'algèbre de Hecke générique sont alors plus efficaces. Dans une dernière partie, on établit, pour le cas non-commutatif, l'algorithme classique de minimisation des représentations linéaires des séries rationnelles dû à M. P. Schutzenberger. On montre comment calculer les isomorphismes d'automates minimaux.

Thesis (Ph. D.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2006.
Symington, Margaret, Committee Member ; Howard, Ayanna, Committee Member ; Tannenbaum, Allen, Committee Member ; Verriest, Erik, Committee Member ; Egerstedt, Magnus, Committee Chair. Vita. Includes bibliographical references.

Dans cette these nous proposons un cadre formel complet pour l'analyse des systemes temporises, avec l'accent mis sur la valeur pratique de l'approche. Nous decrivons des systemes commes des automates temporises and nous exprimons les proprietes en logiques temps-reel. Nous considerons deux types d'analyse. Verification : etant donnes un systeme et une propriete, verifier que le systeme satisfait la propriete. Synthese de controleurs : etant donnes un systeme et une propriete, restreindre le systeme pour qu'il satisfasse la propriete. Pour rendre l'approche possible malgre la difficulte theorique des problemes, nous proposons : des abstractions pour reduire l'espace d'etats concret en un espace abstrait beaucoup plus petit qui, pourtant, preserve toutes les proprietes qui nous interessent. Des techniques efficaces pour calculer et explorer l'espace d'etats abstrait. Nous definissons des bisimulations et simulations faisant abstraction du temps et etudions les proprietes qu'elles preservent. Pour les bisimulations, l'analyse consiste a generer d'abord l'espace abstrait, et ensuite l'utiliser pour verifier des proprietes sur l'espace concret. Pour les simulations, la generation et la verification se font en meme temps (a-la-volee). Un algorithme a-la-volee est aussi develope pour la synthese de controleurs. Pour aider l'utilisateur a sa comprehension, nous produisons des sequences diagnostiques concretes. Nous avons implante nos methodes dans kronos, l'outil d'analyse temps-reel de verimag. Nous avons aussi connecte kronos a open-caesar. Nous avons traite un nombre d'etudes de cas non-triviales : deux protocoles industriels de communication par le cnet et bang&olufsen, le circuit electronique asynchrone stari, un langage de documents multimedia develope a inria, un exemple de scheduling temps-reel et un exemple benchmark. L'analyse a parfois revele des erreurs dans les systemes modelises. Les resultats experimentaux ont montre que nous avons reussi a ameliorer la performance par rapport a des versions precedentes de kronos et d'autres outils similaires de plusieurs ordres de grandeur.

Cette thèse constitue un point de départ pour la programmation d'un système de calcul formel sur les automates, les semigroupes et les langages rationnels. On y trouve la caractérisation des automates construits selon l'algorithme de Glushkov. Des caractérisations de familles de langages testables à partir de leurs automates minimaux y sont également décrites. Le logiciel AGL regroupe un ensemble de packages Maple sur les automates, les semigroupes et les langages rationnels. L'ensemble des algorithmes déduits des caractérisations y est implémenté. Ce logiciel constitue un prototype pour un système de calcul formel dédié aux automates, aux semigroupes et aux langages rationnels.

Nous étudions dans cette thèse des structures généralisant la notion classique de mot. Elles sont construites à partir d’un ensemble partiellement ordonné (partially ordered set ou poset) vérifiant les propriétés suivantes : — elles ne contiennent pas 4 éléments distincts x, y, z, t dont l’ordre relatif est exactement x < y, z < y, z < t (posets dits sans N) ; — les chaînes sont des ordres linéaires dénombrables et dispersés ; — les antichaînes sont finies ; et chaque élément est étiqueté par une lettre d’un alphabet fini. De manière équivalente, la classe des posets que nous considérons est la plus petite construite à partir du poset vide et du singleton, fermée par les produits séquentiel et parallèle finis, et le produit ω et son renversé −ω (posets série-parallèles). Elle est une généralisation à la fois des posets série-parallèles finis étiquetés, en y ajoutant l’infinitude, et des mots transfinis, en affaiblissant l’ordre total des éléments en ordre partiel. En informatique, les posets série-parallèles finis trouvent leur intérêt dans la modélisation des processus concurrents basés sur les primitives fork/join, et les mots transfinis dans l’étude de la récursivité. Les langages rationnels de ces posets étiquetés sont définis à partir d’expressions et d’automates équivalents introduits par Bedon et Rispal, qui généralisent le cas des mots transfinis (Bruyère et Carton) et celui des posets finis (Lodaya et Weil). Dans cette thèse nous les étudions du point de vue de la logique. Nous généralisons en particulier le théorème de Büchi, Elgot et Trakhtenbrot, établissant pour le cas des langages de mots finis l’égalité entre la classe des langages rationnels et celle des langages définissables en logique monadique du second ordre (MSO). La logique mise en oeuvre est une extension de MSO par de l’arithmétique de Presburger. Nous nous intéressons également à certaines variétés d’algèbres de posets. Nous montrons que l’algèbre dont l’univers est la classe des posets série-parallèles transfinis et dont les opérations sont les produits séquentiel et parallèle finis et les produits (resp. puissances) ω et − ω est libre dans la variété correspondante V (resp. V 0). Nous en déduisons la liberté de la même algèbre sans le produit parallèle ou le produit − ω. Enfin, nous montrons que la théorie équationnelle de V 0 est décidable. Ce sont notamment des généralisations de résultats similaires de Bloom et Choffrut pour la variété d’algèbres de mots de longueur inférieure à ω!, de Choffrut et Ésik pour la variété d’algèbres de posets sans N dont les antichaînes sont finies et les chaînes sont de longueur inférieure à ω! et ceux de Bloom et Ésik pour la variété d’algèbres de mots sur les ordres linéaires dénombrables et dispersés
We study in this thesis structures extending the classical notion of word. They are built from a partially ordered set (poset) verifying the following properties : — they do not contain 4 distinct elements x, y, z, t whose relative order is exactly x < y, z < y, z < t (posets called N-free) ; — their chains are countable and scattered linear orderings ; — their antichains are finite ; and each element is labeled by a letter of a finite alphabet. Equivalently, the class of posets which we consider is the smallest one built from the empty poset and the singleton, and being closed under sequential and parallel products, and ω product and its backward ordering −ω (series-parallel posets). It is a generalization of both of finite series-parallel labeled posets, by adding infinity, and transfinite words, by weakening the total ordering of the elements to a partial ordering. In computer science, series-parallel posets find their interest in modeling concurrent processes based on fork/join primitives, and transfinite words in the study of recursion. The rational languages of these labeled posets are defined from expressions and equivalent automata introduced by Bedon and Rispal, which generalize thecase of transfinite words (Bruyère and Carton) and the one of finite posets (Lodaya and Weil). In this thesis we study such structures from the logic point of view. In particular, we generalize the Büchi-Elgot-Trakhtenbrot theorem, establishing in the case of finite words the correspondence between the class of rational languages and the one of languages definable in monadic second order logic (MSO). The implemented logic is an extension of MSO by Presburger arithmetic. We focus on some varieties of posets algebras too. We show that the algebra whose universe is the class of transfinite series-parallel posets and whose operations are the sequential and parallel products and the ω and −ω products (resp. powers) is free in the corresponding variety V (resp. V 0). We deduce the freeness of the same algebra without parallel or −ω product. Finally, we showthat the equational theory of V 0 is decidable. These results are, in particular, generalizations of similar results of Bloom and Choffrut on the variety of algebras of words whose length are less than ω!, of Choffrut and Ésik on the variety of algebras of N-free posets whose antichains are finite and whose chains are less than ω! and those of Bloom and Ésik on the variety of algebras of words indexed by countable and scattered linear orderings

Dependent type theories are a kind of mathematical foundations investigated both for the formalisation of mathematics and for reasoning about programs. They are implemented as the kernel of many proof assistants and programming languages with proofs (Coq, Agda, Idris, Dedukti, Matita, etc). Dependent types allow to encode elegantly and constructively the universal and existential quantifications of higher-order logics and are therefore adapted for writing logical propositions and proofs. However, their usage is not limited to the area of pure logic. Indeed, some recent work has shown that they can also be powerful for driving the construction of programs. Using more precise types not only helps to gain confidence about the program built, but it can also help its construction, giving rise to a new style of programming called Type-Driven Development. However, one difficulty with reasoning and programming with dependent types is that proof obligations arise naturally once programs become even moderately sized. For example, implementing an adder for binary numbers indexed over their natural number equivalents naturally leads to proof obligations for equalities of expressions over natural numbers. The need for these equality proofs comes, in intensional type theories (like CIC and ML) from the fact that in a non-empty context, the propositional equality allows us to prove as equal (with the induction principles) terms that are not judgementally equal, which implies that the typechecker can't always obtain equality proofs by reduction. As far as possible, we would like to solve such proof obligations automatically, and we absolutely need it if we want dependent types to be use more broadly, and perhaps one day to become the standard in functional programming. In this thesis, we show one way to automate these proofs by reflection in the dependently typed programming language Idris. However, the method that we follow is independent from the language being used, and this work could be reproduced in any dependently-typed language. We present an original type-safe reflection mechanism, where reflected terms are indexed by the original Idris expression that they represent, and show how it allows us to easily construct and manipulate proofs. We build a hierarchy of correct-by-construction tactics for proving equivalences in semi-groups, monoids, commutative monoids, groups, commutative groups, semi-rings and rings. We also show how each tactic reuses those from simpler structures, thus avoiding duplication of code and proofs. Finally, and as a conclusion, we discuss the trust we can have in such machine-checked proofs.

Dans cette thèse nous proposons un cadre formel complet pour l'analyse des systèmes temporisés, avec l'accent mis sur la valeur pratique de l'approche. Nous décrivons des systèmes comme des automates temporisés et nous exprimons les propriétés en logiques temps-réel. Nous considérons deux types d'analyse. Vérification : étant donnés un système et une propriété, vérifier que le système satisfait la propriété. Synthèse de contrôleurs : étant donnés un système et une propriété, restreindre le système pour qu'il satisfasse la propriété. Pour rendre l'approche possible malgré la difficulté théorique des problèmes, nous proposons : Des abstractions pour réduire l'espace d'états concret en un espace abstrait beaucoup plus petit qui, pourtant, préserve toutes les propriétés qui nous intéressent. Des techniques efficaces pour calculer et explorer l'espace d'états abstrait. Nous définissons des bisimulations et simulations faisant abstraction du temps et nous étudions les propriétés qu'elles préservent. Pour les bisimulations, l'analyse consiste à générer d'abord l'espace abstrait, et ensuite l'utiliser pour vérifier des propriétés sur l'espace concret. Pour les simulations, la génération et la vérification se font en même temps (à-la-volée). Un algorithme à-la-volée est aussi développé pour la synthèse de contrôleurs. Pour aider l'utilisateur à sa compréhension du système, nous produisons des séquences diagnostiques concrètes. Nous avons implanté nos méthodes dans Kronos, l'outil d'analyse temps-réel de Verimag, et nous avons traité un nombre d'études de cas réalistes parmi lesquelles le protocole FRP-DT de réservation rapide de débit pour les réseaux ATM (dans le cadre d'une coopération scientifique avec le CNET), le protocole de détection de collisions dans un réseaux à accès multiple de Band&Olufsen, l'ordonnancement de tâches temps-réel périodiques, la cohérence et l'ordonnancement des documents multimédia, ainsi qu'un nombre d'études de cas benchmarks, telles que le protocole d'exclusion mutuelle de Fischer, les protocoles de communication CSMA/CD et FDDI.

The new Field Programmable Gate Array (FPGA) technologies and their structures have opened up new approaches to logic design and synthesis. The main feature of an FPGA is an array of logic blocks surrounded by a programmable interconnection structure. Cellular FPGAs are a special class of FPGAs which are distinguished by their fine granularity and their emphasis on local cell interconnects. While these characteristics call for specialized synthesis tools, the availability of logic gates other than Boolean AND, OR and NOT in these architectures opens up new possibilities for synthesis. Among the possible realizations of Boolean functions, XOR logic is shown to be more compact than AND/OR and also highly testable. In this dissertation, the concept of structural regularity and the advantages of XOR logic are used to investigate various synthesis approaches to cellular FPGAs, which up to now have been mostly nonexistent. Universal XOR Canonical Forms, Two-level AND/XOR, restricted factorization, as well as various Directed Acyclic Graph structures are among the proposed approaches. In addition, a new comprehensive methodology for the investigation of all possible XOR canonical forms is introduced. Additionally, a new compact class of XOR-based Decision Diagrams for the representation of Boolean functions, called Kronecker Functional Decision Diagrams (KFDD), is presented. It is shown that for the standard, hard, benchmark examples, KFDDs are on average 35% more compact than Binary Decision Diagrams, with some reductions of up to 75% being observed.

Cette thèse contribue à une recherche de modèles finis et à la démonstration automatisée de théorèmes, en se concentrant principalement, mais sans s'y limiter, sur les méthodes d'intelligence artificielle. Dans la première partie, nous résolvons une question de recherche ouverte à partir de l'algèbre abstraite en utilisant une recherche automatisée de modèles finis massivement parallèles, en utilisant l'assistant de preuve Isabelle. À savoir, nous établissons l'indépendance de certaines lois de distributivité abstraites dans les binaires résiduels dans le cas général. En tant que sous-produit de cette découverte, nous apportons un client Python au serveur Isabelle. Le client a déjà trouvé son application dans les travaux d'autres chercheurs et de l'enseignement supérieur. Dans la deuxième partie, nous proposons une architecture de réseau neuronal génératif pour produire des modèles finis de structures algébriques appartenant à une variété donnée d'une manière inspirée des modèles de génération d'images tels que les GAN (réseaux antagonistes génératifs) et les autoencodeurs. Nous contribuons également à un paquet Python pour générer des semi-groupes finis de petite taille comme implémentation de référence de la méthode proposée. Dans la troisième partie, nous concevons une architecture générale de guidage des vérificateurs de saturation avec des algorithmes d'apprentissage par renforcement. Nous contribuons à une collection d'environnements compatibles OpenAI Gym pour diriger Vampire et iProver et démontrons sa viabilité sur des problèmes sélectionnés de la bibliothèque TPTP (Thousand of Problems for Theorem Provers). Nous contribuons également à une version conteneurisée d'un modèle ast2vec existant et montrons son applicabilité à l'incorporation de formules logiques écrites sous la forme clausal-normale. Nous soutenons que l'approche modulaire proposée peut accélérer considérablement l'expérimentation de différentes représentations de formules logiques et de schémas de génération de preuves synthétiques à l'avenir, résolvant ainsi le problème de la rareté des données, limitant notoirement les progrès dans l'application des techniques d'apprentissage automatique pour la démonstration automatisée de théorèmes
This thesis contributes to a finite model search and automated theorem proving, focusing primarily but not limited to artificial intelligence methods. In the first part, we solve an open research question from abstract algebra using an automated massively parallel finite model search, employing the Isabelle proof assistant. Namely, we establish the independence of some abstract distributivity laws in residuated binars in the general case. As a by-product of this finding, we contribute a Python client to the Isabelle server. The client has already found its application in the work of other researchers and higher education. In the second part, we propose a generative neural network architecture for producing finite models of algebraic structures belonging to a given variety in a way inspired by image generation models such as GANs (generative adversarial networks) and autoencoders. We also contribute a Python package for generating finite semigroups of small size as a reference implementation of the proposed method. In the third part, we design a general architecture of guiding saturation provers with reinforcement learning algorithms. We contribute an OpenAI Gym-compatible collection of environments for directing Vampire and iProver and demonstrate its viability on select problems from the Thousands of Problems for Theorem Provers (TPTP) library. We also contribute a containerised version of an existing ast2vec model and show its applicability to embedding logical formulae written in the clausal-normal form. We argue that the proposed modular approach can significantly speed up experimentation with different logic formulae representations and synthetic proof generation schemes in future, thus addressing the data scarcity problem, notoriously limiting the progress in applying the machine learning techniques for automated theorem proving

Model checking is an automatic formal verification technique for establishing correctness of systems. It has been widely used in industry for analysing and verifying complex safety-critical systems in application domains such as avionics, medicine and computer security, where manual testing is infeasible and even minor errors could have dire consequences. In our increasingly parallelised world, concurrency has become pivotal and seamlessly woven within programming paradigms, however, extremely challenging when it comes to modelling and establishing correctness of intended behaviour. Tools for model checking concurrent systems face severe limitations due to scalability problems arising from the need to examine all possible interleavings (schedules) of executions of parallel components. Moreover, concurrency poses additional challenges to model checking, giving rise to phenomena such as nondeterminism, deadlock, livelock, etc. In this thesis we focus on adapting and developing novel model-checking techniques for concurrent systems in the setting of the process algebra CSP and its primary model checker FDR. CSP allows for a compact modelling and precise analysis of event-based concurrency, grounded on synchronous message passing as a fundamental mechanism of inter-component communication. In particular, we investigate techniques based on symbolic model checking, static analysis and abstraction, all of them exploiting the compositionality inherent in CSP and targeting to increase the scale of systems that can be tractably analysed. Firstly, we investigate symbolic model-checking techniques based on Boolean satisfiability (SAT), which we adapt for the traces model of CSP. We tailor bounded model checking (BMC), that can be used for bug detection, and temporal k-induction, which aims at establishing inductiveness of properties and is capable of both bug finding and establishing the correctness of systems. Secondly, we propose a static analysis framework for establishing livelock freedom of CSP processes, with lessons for other concurrent formalisms. As opposed to traditional exhaustive state-space exploration, our framework employs a system of rules on the syntax of a process to calculate a sound approximation of its fair/co-fair sets of events. The rules either safely classify a process as livelock-free or report inconclusiveness, thereby trading accuracy for speed. Finally, we develop a series of abstraction/refinement schemes for the traces, stable-failures and failures-divergences models of CSP and embed them into a fully automated and compositional CEGAR framework. For each of those techniques we present an implementation and an experimental evaluation on a set of CSP benchmarks.

Les règles de transformation des problèmes equationnels sont donnes permettant, en particulier, de décider de l'existence d'une solution fermée. Comme première application, il est montre comment calculer une grammaire pour le langage des termes fermes irréductibles par un système de réécriture. D'autres applications et extensions sont ensuite envisagées. En particulier, en programmation logique et dans les spécifications algébriques

The specification of a decoder, i.e., a program that translates sentences from one natural language into another, is an intricate process, driven by the application and lacking a canonical methodology. The practical nature of decoder development inhibits the transfer of knowledge between theory and application, which is unfortunate because many contemporary decoders are in fact related to formal-language theory. This thesis proposes an algebraic framework where a decoder is specified by an expression built from a fixed set of operations. As yet, this framework accommodates contemporary syntax-based decoders, it spans two levels of abstraction, and, primarily, it encourages mutual stimulation between the theory of weighted tree automata and the application.

O objetivo deste trabalho é fornecer um atlas das bases de identidades para as variedades geradas por semigrupos e grupos de ordem pequena. Com o propósito de auxiliar os matemáticos que trabalham neste campo a encontrar informações com facilidade, foi implementado um website que executa em segundo plano um conjunto de algoritmos desenvolvidos no âmbito deste trabalho e ainda ferramentas de demonstração automática e construtores de modelos finitos, para que o utilizador tenha um guia automático e inteligente. Por exemplo, o site fornece a primeira lista completa de variedades geradas por semigrupos de ordens iguais ou inferiores a 5, e consegue identificar rapidamente se a variedade gerada por um semigrupo inserido pelo utilizador, mesmo para ordens bastante superiores, coincide com uma das 218 variedades presentes na base de dados (atualmente inclui ainda outras 11 variedades geradas por semigrupos de ordens superiores). O site também fornece bases de identidades para classes arbitrariamente grandes de semigrupos, como bandas, ou a identificação dos semigrupos de ordem 6 conhecidos que geram variedades de base não finita. Além desta base de dados, o site propõe ainda uma lista das variedades geradas pelos semigrupos de ordem 6, num total de 414 conjeturas para novas variedades, entre as 463 identificadas neste trabalho e retirando as 49 variedades já conhecidas. O site disponibiliza ainda a informação para variedades geradas pelos grupos de ordens iguais ou inferiores a 255, obtida em resultado do levantamento e análise da literatura existente sobre as variedades geradas por estes grupos, para um total de 7012 grupos. O tratamento da informação recolhida para variedades geradas por grupos foi efetuado em GAP e através do desenvolvimento de algoritmos específicos para grupos comutativos e grupos metabelianos, nomeadamente para obtenção das identidades especificas de cada grupo, quando possível. O site oferece ainda um conjunto de funções sobre semigrupos, como encontrar o mínimo lexicográfico das cópias isomórficas de um dado semigrupo. Em relação à propriedade de base inerentemente não finita, o site pode decidir se um determinado semigrupo finito possui ou não essa propriedade; calcular a decomposição do semigrupo em semireticulados; ou converter a sintaxe da tabela de multiplicação de um semigrupo para utilização no GAP ou num demonstrador automático de teoremas/construtor de modelos finitos. O site fornece algumas outras funcionalidades, como uma ferramenta que gera a tabela de multiplicação de um semigrupo fornecida por uma apresentação em C, onde C ´e qualquer classe de álgebras definida por um conjunto de fórmulas em predicados de primeira ordem. A operação no sentido inverso também está acessível. O site disponibiliza um conjunto de informações e funcionalidades sobre variedades e as suas bases de identidades, como apresentar todas as inclusões entre as variedades da base de dados (variedades que são sub-variedades de outras variedades, que as contem) em formato gráfico, identificar se a variedade gerada por um semigrupo coincide com uma existente na base de dados, ou identificar a variedade cuja base é equivalente ao conjunto de identidades inseridas pelo utilizador. O site consegue ainda listar todas as variedades da base dados cujas bases de identidades implicam ou são implicadas por um conjunto de identidades definidas pelo utilizador. Neste cálculo o site leva em conta o conhecimento prévio de todas as inclusões entre variedades acima referidas para acelerar o cálculo e minimizar o uso do demonstrador automático de teoremas/construtor de modelos finitos. No desenvolvimento deste site foram utilizados: na implementação de algoritmos no servidor, Python, substituído pela versão compilada Cython em todos os cálculos intensivos; no desenvolvimento da interface cliente, JavaScript, JQuery, Ajax, Flask, HTML5, CSS3, Bootstrap e MathJax; em bases de dados relacionais, MySQL e SQLAlchemy; na preparação da informação presente nas bases de dados: GAP-System e em particular os “packages” smallsemi e smallgroups; na demonstração automática de teoremas e construção de modelos finitos, Prover9 e Mace4; na apresentação de diagramas, Graphviz. Foi desenvolvido um extenso conjunto de algoritmos reutilizáveis, para manipulação de variedades, semigrupos e grupos, organizados em bibliotecas, destacando-se: varlib.pyx – Implementa os algoritmos de cálculo intensivo do site, como o algoritmo que encontra o mínimo lexicográfico das cópias isomorfas de um dado semigrupo, ou o que verifica se um dado semigrupo satisfaz a base de identidades de uma das variedades na base de dados, e não satisfaz as identidades que definem as sub-variedades maximais. Por questões de velocidade, não existe nesta biblioteca recurso a demonstradores automáticos de teoremas ou a construtores de modelos finitos, sendo a sua funcionalidade substituída por algoritmos desenvolvidos otimizados para identidades, correndo nesta biblioteca a uma velocidade tipicamente 1000x superior ao mesmo programa em Python interpretado; p9m4tools.py – Implementa os algoritmos que recorrem ao demonstrador automático de teoremas e construtor de modelos finitos, embora em ´ultimo recurso, por questões de desempenho, através da implementação de diversas técnicas de “cache”. Nesta biblioteca estão por exemplo os algoritmos desenvolvidos para obter um semigrupo e a sua tabela de multiplicação a partir de uma apresentação, e filtrar as variedades cuja bases de identidades implicam, são implicadas por, ou são equivalentes a um conjunto de identidades entradas pelo utilizador; vartools.py – Implementa rotinas de menor exigência computacional, como a interpretação da entrada de dados do utilizador (por exemplo tabelas de multiplicação em diversos formatos à escolha do utilizador) e a formatação dos dados a apresentar, quer em texto que de forma gráfica. Esta biblioteca inclui ainda diversos algoritmos sobre semigrupos, como a decomposição em semireticulados. Este trabalho também contribui para a extensão da base de dados de variedades conhecidas: existem 28634 semigrupos de ordem 6, considerados equivalentes quando isomorfos ou anti-isomorfos. As variedades de 2035 desses semigrupos não coincidem com nenhuma variedade conhecida gerada por semigrupos de ordem até 5. Neste projeto, com base no teorema de Birkhoff e aplicando novos algoritmos de computador e uma ferramenta de demonstração automática de teoremas/construtor de modelo finitos, foi possível dividir esses 2035 semigrupos em 463 conjuntos de semigrupos que satisfazem as mesmas identidades, correspondendo a 414 novas variedades propostas (dado que são já conhecidas 45 variedades de base finita e 4 variedades de base não finita, geradas por semigrupos da ordem 6). Além disso, as identidades candidatas para a bases de identidades para todas estas novas variedades também são propostas e apresentadas nesta tese, acompanhadas por todas as tabelas de Cayley e os IDs no “package” GAPs smallsemi correspondentes, para cada conjunto de semigrupos encontrados que geram a mesma variedade conjeturada. As provas dessas novas variedades representam problemas em aberto e um desafio para todos os matemáticos nesta área. A mesma metodologia pode ser utilizada para encontrar novas variedades candidatas geradas por semigrupos de ordem 7 ou maior (no âmbito deste trabalho foram encontrados 73807 semigrupos não isomorfos de ordem 7 cujas variedades não coincidem com as variedades registadas na base de dados do site). Esta tese começa com um artigo 1 de pesquisa sobre variedades de semigrupos que contém a maior parte do conteúdo matemático desta tese. Este trabalho representa diversas contribuições para o campo do estudo das variedades de semigrupos: pela primeira vez foi reunida a informação dispersa sobre todas as variedades geradas por semigrupos de ordem igual ou inferior a 5, e relativa aos grupos de ordem igual ou inferior a 255, sendo apresentada num site de fácil utilização. O site oferece ainda um conjunto de funcionalidades sobre semigrupos e sobre variedades da base de dados, alicerçadas num conjunto de algoritmos desenvolvidos para maximização da performance e integrando uma interface, transparente para o utilizador, com um demonstrador automático de teorema e um construtor de modelos finitos, funcionando em paralelo para resultados mais rápidos. Adicionalmente, este trabalho contribuiu para o enriquecimento da base de dados de variedades geradas por semigrupos, ao propor conjeturas para todas as variedades não conhecidas geradas por semigrupos de ordem 6 e respetivas bases de identidades. As principais limitações deste trabalho estão relacionadas com o fato de alguns dos algoritmos desenvolvidos exigirem uma utilização intensiva de recursos computacionais (memória e processador). Estes algoritmos, ou não são adequados para colocação no site (como a pesquisa de novas variedades e respetivas bases), ou exigem limitações dos parâmetros de entrada (por exemplo o cálculo do mínimo lexicográfico, a geração de semigrupos a partir de apresentações, e a identificação de variedades, estão limitados a semigrupos de ordem inferior ou igual a, respetivamente, 10, 20 e 100). Noutras situações, embora raras, o site pode atingir o limite de memória permitido a cada utilizador. Este trabalho inspirou um alargado conjunto de ideias para trabalho futuro, e a primeira consiste na criação de um “package” GAP. Além de oferecer tudo o que site oferece e sem as limitações de memória e processador do site, o utilizador pode realizar múltiplas operações de forma automática. Na realidade o grosso do trabalho está pronto, já que este “package” se pode materializar apenas com o desenvolvimento de uma pequena camada de interface de comandos GAP, já que todos os algoritmos do site estão em bibliotecas autónomas e prontos para ser invocados por qualquer programa externo (aliás o acesso pelo GAP a rotinas das bibliotecas do site foi testado com sucesso no âmbito deste trabalho). Outras ideias para trabalho futuro passam por estender a procura de variedades `as variedades geradas por semigrupos de ordem 7; melhorar os algoritmos atuais para propor também as identidades que definem as sub-variedades maximais; automatizar a demonstração das variedades conjeturadas; desenvolver uma interface no site que permita a extensão da base de dados com novas variedades pelos matemáticos; aumentar as funcionalidades sobre variedades de grupos; desenvolver novo algoritmo para acelerar o cálculo do mínimo lexicográfico.
The aim of this work was to provide an atlas of identity bases for varieties generated by small semigroups and groups. To help the working mathematician easily find information, a website was implemented, running in the background automated reasoning tools and finite model builders, so that the user has an automatic intelligent guide on the literature. For instance, the site provide the first complete the list of varieties generated by a semigroup of order up to 5. The website also provides identity bases for several types of semigroups or groups, such as bands, commutative groups, and metabelian groups. Regarding the inherent non-finite basis property, the website can decide whether or not a given finite semigroup possesses this property. The site provides some other functionalities such as a tool that outputs the multiplication table of a semigroup given by a C-presentation, where C is any class of algebras defined by a set of first order formulas. The inverse conversion is also available. This work also gives a contribution to the extension of the database of known varieties: there are 28634 nonisomorphic semigroups of order 6. The varieties of 2035 of these semigroups do not coincide to any known variety generated by semigroups of order up to 5. In this project, building on the Birkhoff theorem and applying new computer algorithms and automatic theorem proving, it was possible to divide these 2035 semigroups into 463 sets of semigroups that satisfy the same identities, corresponding to 414 new proposed varieties (since there are 45 known finitely-based and 4 known non-finitely based varieties generated by semigroups of order 6). Additionally, candidate identities for the identity basis for all these new varieties are also proposed and presented in this thesis, accompanied by all Cayley tables and the corresponding GAP smallsemi package IDs in each set of semigroups found. The proofs of these new varieties represent open problems and a challenge to all mathematicians in this field. The same methodology can be extended to find new candidate varieties generated by semigroups of order 7 or larger (within this work were found 73807 nonisomorphic semigroups of order 7 whose varieties do not coincide with known varieties registered in the site database).