Literatura científica selecionada sobre o tema "Semigroupes finis"

A locally testable semigroup S is a semigroup with the property that for some non-negative integer k, called the order or level of local testability, two words u and v in some set of generators for S are equal in the semigroup if (1) the prefix and suffix of the words of length k coincide, and (2) the set of intermediate substrings of length k of the words coincide. The local testability problem for semigroups is, given a finite semigroup, to decide, if the semigroup is locally testable or not. Recently, we introduced a polynomial time algorithm for the local testability problem and to find the level of local testability for semigroups based on our previous description of identities of k-testable semigroups and the structure of locally testable semigroups. The first part of the algorithm we introduce solves the local testability problem. The second part of the algorithm finds the order of local testability of a semigroup. The algorithm is of order n2, where n is the order of the semigroup.

Given a group [Formula: see text], we study right and left zeros, idempotents, the minimal ideal, left cancelable and right cancelable elements of the semigroup [Formula: see text] of [Formula: see text]-linked upfamilies and characterize groups [Formula: see text] whose extensions [Formula: see text] are commutative. We finish the paper with the complete description of the structure of the semigroups [Formula: see text] for all groups [Formula: see text] of cardinality [Formula: see text].

The problem of describing semigroup varieties with finite planarity rank is researched. In addition to the previously obtained results the author finds two new countable infinite series of semigroup varieties with finite planarity rank.

Abstract Motivated by a problem on the dynamics of compositions of plane hyperbolic isometries, we prove several fundamental results on semigroups of isometries, thought of as real Möbius transformations. We define a semigroup $S$ of Möbius transformations to be semidiscrete if the identity map is not an accumulation point of $S$. We say that $S$ is inverse free if it does not contain the identity element. One of our main results states that if $S$ is a semigroup generated by some finite collection $\mathcal{F}$ of Möbius transformations, then $S$ is semidiscrete and inverse free if and only if every sequence of the form $F_n=f_1\dotsb f_n$, where $f_n\in \mathcal{F}$, converges pointwise on the upper half-plane to a point on the ideal boundary, where convergence is with respect to the chordal metric on the extended complex plane. We fully classify all two-generator semidiscrete semigroups and include a version of Jørgensen’s inequality for semigroups. We also prove theorems that have familiar counterparts in the theory of Fuchsian groups. For instance, we prove that every semigroup is one of four standard types: elementary, semidiscrete, dense in the Möbius group, or composed of transformations that fix some nontrivial subinterval of the extended real line. As a consequence of this theorem, we prove that, with certain minor exceptions, a finitely generated semigroup $S$ is semidiscrete if and only if every two-generator semigroup contained in $S$ is semidiscrete. After this we examine the relationship between the size of the “group part” of a semigroup and the intersection of its forward and backward limit sets. In particular, we prove that if $S$ is a finitely generated nonelementary semigroup, then $S$ is a group if and only if its two limit sets are equal. We finish by applying some of our methods to address an open question of Yoccoz.

Non-commutative cryptography studies cryptographic primitives and systems which are based on algebraic structures like groups, semigroups and noncommutative rings. We continue to investigate inverse protocols of Non-commutative cryptography defined in terms of subsemigroups of Affine Cremona Semigroups over finite fields or arithmetic rings Zm and homomorphic images of these semigroups as possible instruments of Post Quantum Cryptography. This approach allows to construct cryptosystem which are not public keys, when protocol finish correspondents have mutually inverse transformations on affine space Kn or variety (K*)n where K is the field or arithmetic ring. The security of such inverse protocol rests on the complexity of word problem to decompose element of Affine Cremona Semigroup given in its standard form into composition of given generators. We discuss the idea of usage combinations of two cryptosystems with cipherspaces(K*)n and Kn to form a new cryptosystem with the plainspace(K*)n, ciphertextKn and nonbijective highly nonlinear encryption map.

This research studies two systems composed by the Timoshenko beam model for double‐wall carbon nanotubes, coupled with the heat equation governed by Fourier's law. For the first system, the coupling is given by the rotation speed of the vertical filament in the beam from the first beam of Timoshenko and the Laplacian of temperature , where we also consider the damping terms fractionals , , and , where . For this first system, we proved that the semigroup associated to system decays exponentially for all . The second system also has three fractional dampings , , and , with . Furthermore, the couplings between the heat equation and the Timoshenko beams of the double wall carbon nanotubes for the second system are given by the Laplacian of the rotation speed of the vertical filament in the beam of the first beam of Timoshenko and the Lapacian of temperature . For the second system, we prove the exponential decay of the associated semigroup for and also show that this semigroup admits Gevrey classes for , and we finish our investigation proving that is analytic when the parameters .

Le calcul et la décidabilité du supremum de deux pseudo variétés de semi groupes est un problème difficile en dépit de son apparente simplicité. L'exemple le plus surprenant est du à Albert, Baldinger et Rhodes (1992): Le supremum de deux pseudo équationnelles de bases finies, donc décidables peut ne pas être décidable. À l'aide de la théorie des opérations implicites, nous résolvons deux problèmes ouverts de ce type proposés dans le traité d'Almeida semigrupos finitos e algebra universal, publicacoes do instituto de matematica e estatistica da universidade de Sao Paulo: d'une part, la pseudo variété j b n'est pas de base finie mais est décidable; d'autre part, une formulation explicite de la pseudo variété li b est donnée. Les preuves sont basées sur des arguments topologiques et algébriques d'une part, combinatoires d'autre part

Cette these est une contribution a l'etude de la structure du treillis des pseudo-varietes de semigroupes, et de la correspondance d'eilenberg, qui associe bijectivement a chaque pseudo-variete de semigroupes une variete de langages. Dans un premier moment nous calculons tous les suprema de la forme v w ou v est l'une des pseudo-varietes li, k, d ou n et ou w est une sous-pseudo-variete du produit de mal'cev de cr par n. De plus, nous donnons une description de la structure des semi-groupes d'operations implicites sur diverses sous-pseudo-varietes de do et de ldg. Comme application nous calculons plusieurs suprema impliquant ces dernieres pseudo-varietes. Dans une deuxieme phase nous nous sommes interesse aux classes de langages associees. Nous profitons de l'etude precedente, conduite sur les semigroupes d'operations implicites sur diverses sous-pseudo-varietes de do et de ldg pour donner des descriptions combinatoires des classes de languages reconnus par chacune de ces pseudo-varietes. Nous etudions, en outre, quelques classes de langages definies a partir de la notion de langage localement testable par l'introduction de petites variations sur cette notion, notamment l'introduction de compteurs et de lateralisation. On termine ce travail en retournant aux operations implicites. Cette fois on etudie les semigroupes d'operations implicites sur lj 1. A partir d'un resultat d'almeida et weil nous obtenons une caracterisation qui constitue un progres mais qui n'est pas encore satisfaisante. Cependant elle permet de deduire quelques proprietes interessantes et non triviales des semigroupes localement idempotents et localement commutatifs.

Les langages réguliers, langages calculés par automates finis, sont parmi les objets les plus simples de l'informatique théorique. Cette thèse étudie plusieurs modèles de calculs: le calcul parallèle avec les circuits booléens, le traitement en flot de documents structurés, et la maintenance d'information sur une structure soumise à des mises à jour incrémentales. Pour ce dernier modèle, les structures auxiliaires sont soit stockées en RAM, soit représentées par des bases de données mises à jour par des formules logiques.Cette thèse étudie les ressources nécessaires pour calculer des classes de langages réguliers dans chacun de ces modèles. Les méthodes employées exploitent l'interaction entre algèbre, logique et combinatoire, en mettant notamment à profit la théorie des semigroupes finis. Cette approche de la complexité s'est notamment montrée extrêmement fructueuse dans le cadre des circuits booléens, où les langages réguliers jouent un rôle central. Cette angle de recherche a été cristallisé par Howard Straubing dans son livre "Finite Automata, Formal Logic, and Circuit Complexity'', où il émet la conjecture que tout langage régulier définissable par une formule arbitraire d'un fragment de logique peut être réécrite en utilisant uniquement des prédicats simples, c'est-à-dire réguliers.Le premier but de ce manuscrit est de prouver cette conjecture dans le cas du fragment Sigma2 de la logique du premier-ordre avec une seule alternance de quantification. Un deuxième résultat propose une description de la complexité en espace, dans le modèle de flot, pour vérifier des propriétés régulières sur des arbres. Une attention particulière est portée aux propriétés vérifiables en espace constant et logarithmique. Un troisième objectif est de décrire tous les langages réguliers d'arbres pouvant être maintenus incrémentalement en temps constant en RAM. Enfin, une dernière partie porte sur le développement de formules logiques efficaces pour maintenir tous les langages réguliers dans le modèle relationnel
Regular languages, languages computed by finite automata, are among the simplest objects in theoretical computer science. This thesis explores several computation models: parallel computing with Boolean circuits, structured document streaming processing, and information maintenance on a structure subject to incremental updates. For the latter, auxiliary structures are either stored in RAM or represented by databases updated by logical formulae.This thesis investigates the resources required to compute classes of regular languages in each of these models. The methods employed rely on the interaction between algebra, logic, and combinatorics, notably exploiting the theory of finite semigroups. This approach of complexity has proven extremely fruitful, particularly in the context of Boolean circuits, where regular languages play a central role. This research angle was crystallised by Howard Straubing in his book "Finite Automata, Formal Logic, and Circuit Complexity", where he conjectured that any regular language definable by an arbitrary formula from a logic fragment can be rewritten to use only simple, regular predicates.The first objective of this manuscript is to prove this conjecture in the case of the Sigma2 fragment of first-order logic with a single alternation of quantification. A second result provides a description of space complexity, in the streaming model, for verifying regular properties on trees. Special attention is given to properties verifiable in constant and logarithmic space. A third objective is to describe all regular tree languages that can be incrementally maintained in constant time in RAM. Finally, a last part focuses on the development of efficient logical formulae for maintaining all regular languages in the relational model

Dans cette thèse, on se propose d'étudier les automates de Mealy, c'est-à-dire des transducteurs complets déterministes lettre à lettre ayant même alphabet d'entrée et de sortie. Ces automates sont utilisés depuis les années 60 pour engendrer des (semi-)groupes qui ont parfois des propriétés remarquables, permettant ainsi de résoudre plusieurs problèmes ouverts en théorie des (semi-)groupes. Dans ce travail, on s’intéresse plus particulièrement aux apports possibles de l'informatique théorique à l'étude de ces (semi-)groupes engendrés par automate. La thèse présentée s'articule autours de deux grands axes. Le premier, qui correspond aux chapitres II et III, traite des problèmes de décision et plus spécifiquement du problème de Burnside dans le chapitre II et des points singuliers dans le chapitre III. Dans ces deux chapitres on met en lien des propriétés structurelles de l'automate avec des propriétés du groupe engendré ou de son action. Le second axe, représenté par le chapitre IV, se rapporte à la génération aléatoire de groupes finis. On cherche, en tirant des automates de Mealy aléatoirement dans des classes spécifiques, à engendrer des groupes finis, et on aboutit à un résultat de convergence pour la distribution ainsi obtenue. Ce résultat fait écho au théorème de Dixon pour les groupes de permutations aléatoires
In this thesis, we study Mealy automata, i.e. complete, deterministic, letter-to-letter transducers which have same input and output alphabet. These automata have been used since the 60s to generate (semi)groups that sometimes have remarkable properties, that were used to solve several open problems in (semi)group theory. In this work, we focus more specifically on the possible contributions that theoretical computer science can bring to the study of these automaton (semi)groups.The thesis consists of two main axis. The first one, which corresponds to the Chapters II and III, deals with decision problems and more precisely with the Burnside problem in Chapter II and with singular points in Chapter III. In these two chapters, we link structural properties of the automaton with properties of the generated group or of its action. The second axis, which comprises the Chapter IV, is related with random generation of finite groups. We seek, by drawing random Mealy automata in specific classes, to generate finite groups, and obtain a convergence result for the obtained distribution. This result echoes Dixon's theorem on random permutation groups

Ce travail est une contribution à l'étude de la limite singulière des équations et des systèmes de Réaction-Diffusion. Ces derniers modélisent des problèmes issus de la physique, de la chimie, de la biologie et des sciences de la technologie. En effet, ce type de problème se présente dans la nature et sont caractérisés par la présence de paramètres qui, lorsqu' ils sont suffisamment grands, donnent lieu généralement à un phénomène appelé couches limites. Cette thèse est composée de cinq chapitres traitant les limites singulières des équations et des systèmes de Réaction Diffusion ainsi que l' existence et l'unicité de solution pour un problème d'obstacle et de quelques EDPs elliptique-parabolique doublement non linéaire avec un opérateur de type Leray Lions. Dans le premier chapitre, nous présentons des résultats théoriques et abstraits sur les limites singulières, où nous traitons aussi la compétition entre deux ou plusieurs opérateurs. Nous appliquons ces résultats dans le contexte des équations aux dérivées partielles et nous étudions le comportement de la solution d'un modèle, lorsque les coefficients de diffusion et/ou de réaction deviennent très grands. Dans les deux chapitres qui suivent, nous considérons un système de réaction diffusion intervenant dans des modèles (macroscopiques) de diffusion dans un milieu hétérogène. Nous présentons d'abord une analyse mathématique (existence et unicité de la solution), ensuite nous étudions le comportement de la solution lorsque le paramètre d'homogénéité devient très grand sur un sous domaine. Le chapitre trois est dédié à l'analyse numérique d'un modèle linéaire, nous prouvons l' existence d'une solution approchée satisfaisant des propriétés de stabilité et de convergence vers la solution du problème continu indépendamment du paramètre d'homogénéité. Le chapitre quatre a pour objet l'étude de l'existence et l'unicité de la solution d'un problème d'obstacle doublement non linéaire avec des contraintes bilatérales, dépendantes de l'espace. Enfin, dans le cinquième chapitre, nous présentons une généralisation des résultats du chapitre trois au cas d'un opérateur de type Leray-Lions et une réaction qui dépend de l'espace.

L'objectif principal de cette thèse consiste à étudier plusieurs thématiques : l'étude de l'observation et la commande d'un système de structure flexible et l'étude de la stabilité asymptotique d'un système d'échangeurs thermiques. Ce travail s'inscrit dans le domaine du contrôle des systèmes décrits par des équations aux dérivées partielles (EDP). On s'intéresse au système du corps-poutre en rotation dont la dynamique est physiquement non mesurable. On présente un observateur du type Luenberger de dimension infinie exponentiellement convergent afin d'estimer les variables d'état. L'observateur est valable pour une vitesse angulaire en temps variant autour d'une constante. La vitesse de convergence de l'observateur peut être accélérée en tenant compte d'une seconde étape de conception. La contribution principale de ce travail consiste à construire un simulateur fiable basé sur la méthode des éléments finis. Une étude numérique est effectuée pour le système avec la vitesse angulaire constante ou variante en fonction du temps. L'influence du choix de gain est examinée sur la vitesse de convergence de l'observateur. La robustesse de l'observateur est testée face à la mesure corrompue par du bruit. En mettant en cascade notre observateur et une loi de commande stabilisante par retour d'état, on souhaite obtenir une stabilisation globale du système. Des résultats numériques pertinents permettent de conjecturer la stabilité asymptotique du système en boucle fermée. Dans la seconde partie, l'étude est effectuée sur la stabilité exponentielle des systèmes d'échangeurs thermiques avec diffusion et sans diffusion. On établit la stabilité exponentielle du modèle avec diffusion dans un espace de Banach. Le taux de décroissance optimal du système est calculé pour le modèle avec diffusion. On prouve la stabilité exponentielle dans l'espace Lp pour le modèle sans diffusion. Le taux de décroissance n'est pas encore explicité dans ce dernier cas.

Cette thèse est centrée autour de l'étude théorique et de l'analyse numérique des équations paraboliques non linéaires avec divers conditions aux limites. La première partie est consacrée aux équations paraboliques dégénérées mêlant des phénomènes non-linéaires de diffusion et de transport. Nous définissons des notions de solutions entropiques adaptées pour chacune des conditions aux limites (flux nul, Robin, Dirichlet). La difficulté principale dans l'étude de ces problèmes est due au manque de régularité du flux pariétal pour traiter les termes de bords. Ceci pose un problème pour la preuve d'unicité. Pour y remédier, nous tirons profit du fait que ces résultats de régularités sur le bord sont plus faciles à obtenir pour le problème stationnaire et particulièrement en dimension un d'espace. Ainsi par la méthode de comparaison "fort-faible" nous arrivons à déduire l'unicité avec le choix d'une fonction test non symétrique et en utilisant la théorie des semi-groupes non linéaires. L'existence de solution se démontre en deux étapes, combinant la méthode de régularisation parabolique et les approximations de Galerkin. Nous développons ensuite une approche directe en construisant des solutions approchées par un schéma de volumes finis implicite en temps. Dans les deux cas, on combine les estimations dans les espaces fonctionnels bien choisis avec des arguments de compacité faible ou forte et diverses astuces permettant de passer à la limite dans des termes non linéaires. Notamment, nous introduisons une nouvelle notion de solution appelée solution processus intégrale dont l'objectif, dans le cadre de notre étude, est de pallier à la difficulté de prouver la convergence vers une solution entropique d'un schéma volumes finis pour le problème de flux nul au bord. La deuxième partie de cette thèse traite d'un problème à frontière libre décrivant la propagation d'un front de combustion et l'évolution de la température dans un milieu hétérogène. Il s'agit d'un système d'équations couplées constitué de l'équation de la chaleur bidimensionnelle et d'une équation de type Hamilton-Jacobi. L'objectif de cette partie est de construire un schéma numérique pour ce problème en combinant des discrétisations du type éléments finis avec les différences finies. Ceci nous permet notamment de vérifier la convergence de la solution numérique vers une solution onde pour un temps long. Dans un premier temps, nous nous intéressons à l'étude d'un problème unidimensionnel. Très vite, nous nous heurtons à un problème de stabilité du schéma. Cela est dû au problème de prise en compte de la condition de Neumann au bord. Par une technique de changement d'inconnue et d'approximation nous remédions à ce problème. Ensuite, nous adaptons cette technique pour la résolution du problème bidimensionnel. A l'aide d'un changement de variables, nous obtenons un domaine fixe facile pour la discrétisation. La monotonie du schéma obtenu est prouvée sous une hypothèse supplémentaire de propagation monotone qui exige que la frontière libre se déplace dans les directions d'un cône prescrit à l'avance.