Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.

Cohomologie de fibrés en droite sur le fibré cotangent de variétés grassmanniennes généralisées

Cette thèse s'intéresse à la cohomologie de fibrés en droite sur le fibré cotangent de variétés projectives. Plus précisément, pour $G$ un groupe algébrique simple, connexe et simplement connexe, $P$ un sous-groupe maximal de $G$ et $\omega$ un générateur dominant du groupe de caractères de $P$, on cherche à comprendre les groupes de cohomologie $H^i(T^*(G/P),\mathcal{L})$ où $\mathcal{L}$ est le faisceau des sections d'un fibré en droite sur $T^*(G/P)$. Sous certaines conditions, nous allons montrer qu'il existe un isomorphisme, à graduation près, entre $H^i(T^*(G/P),\mathcal{L})$ et $H^i(T^*(G/P),\mathcal{L}^{\vee})$ Après avoir travaillé dans un contexte théorique, nous nous intéresserons à certains sous-groupes paraboliques en lien avec les orbites nilpotentes. Dans ce cas, l'algèbre de Lie du radical unipotent de $P$, que nous noterons $\nLie$, a une structure d'espace vectoriel préhomogène. Nous pourrons alors déterminer quels cas vérifient les hypothèses nécessaires à la preuve de l'isomorphisme en montrant l'existence d'un $P$-covariant $f$ dans $\comp[\nLie]$ et en étudiant ses propriétés. Nous nous intéresserons ensuite aux singularités de la variété affine $V(f)$. Nous serons en mesure de montrer que sa normalisation est à singularités rationnelles.

Analyse de groupe d’un modèle de la plasticité idéale planaire et sur les solutions en termes d’invariants de Riemann pour les systèmes quasilinéaires du premier ordre

Les objets d’étude de cette thèse sont les systèmes d’équations quasilinéaires du premier ordre. Dans une première partie, on fait une analyse du point de vue du groupe de Lie classique des symétries ponctuelles d’un modèle de la plasticité idéale. Les écoulements planaires dans les cas stationnaire et non-stationnaire sont étudiés. Deux nouveaux champs de vecteurs ont été obtenus, complétant ainsi l’algèbre de Lie du cas stationnaire dont les sous-algèbres sont classifiées en classes de conjugaison sous l’action du groupe. Dans le cas non-stationnaire, une classification des algèbres de Lie admissibles selon la force choisie est effectuée. Pour chaque type de force, les champs de vecteurs sont présentés. L’algèbre ayant la dimension la plus élevée possible a été obtenues en considérant les forces monogéniques et elle a été classifiée en classes de conjugaison. La méthode de réduction par symétrie est appliquée pour obtenir des solutions explicites et implicites de plusieurs types parmi lesquelles certaines s’expriment en termes d’une ou deux fonctions arbitraires d’une variable et d’autres en termes de fonctions elliptiques de Jacobi. Plusieurs solutions sont interprétées physiquement pour en déduire la forme de filières d’extrusion réalisables. Dans la seconde partie, on s’intéresse aux solutions s’exprimant en fonction d’invariants de Riemann pour les systèmes quasilinéaires du premier ordre. La méthode des caractéristiques généralisées ainsi qu’une méthode basée sur les symétries conditionnelles pour les invariants de Riemann sont étendues pour être applicables à des systèmes dans leurs régions elliptiques. Leur applicabilité est démontrée par des exemples de la plasticité idéale non-stationnaire pour un flot irrotationnel ainsi que les équations de la mécanique des fluides. Une nouvelle approche basée sur l’introduction de matrices de rotation satisfaisant certaines conditions algébriques est développée. Elle est applicable directement à des systèmes non-homogènes et non-autonomes sans avoir besoin de transformations préalables. Son efficacité est illustrée par des exemples comprenant un système qui régit l’interaction non-linéaire d’ondes et de particules. La solution générale est construite de façon explicite.

Bounding The Hochschild Cohomological Dimension

Ce mémoire a deux objectifs principaux. Premièrement de développer et interpréter les groupes de cohomologie de Hochschild de basse dimension et deuxièmement de borner la dimension cohomologique des k-algèbres par dessous; montrant que presque aucune k-algèbre commutative est quasi-libre.

Caractérisation des réponses du PMLS au mouvement de deuxième ordre (modulé par le contraste)

La perception visuelle ne se résume pas à la simple perception des variations de la quantité de lumière qui atteint la rétine. L’image naturelle est en effet composée de variation de contraste et de texture que l’on qualifie d’information de deuxième ordre (en opposition à l’information de premier ordre : luminance). Il a été démontré chez plusieurs espèces qu’un mouvement de deuxième ordre (variation spatiotemporelle du contraste ou de la texture) est aisément détecté. Les modèles de détection du mouvement tel le modèle d’énergie d’Adelson et Bergen ne permettent pas d’expliquer ces résultats, car le mouvement de deuxième ordre n’implique aucune variation de la luminance. Il existe trois modèles expliquant la détection du mouvement de deuxième ordre : la présence d’une circuiterie de type filter-rectify-filter, un mécanisme de feature-tracking ou simplement l’existence de non-linéarités précoces dans le traitement visuel. Par ailleurs, il a été proposé que l’information visuelle de deuxième ordre soit traitée par une circuiterie neuronale distincte de celle qui traite du premier ordre. Bon nombre d’études réfutent cependant cette théorie et s’entendent sur le fait qu’il n’y aurait qu’une séparation partielle à bas niveau. Les études électrophysiologiques sur la perception du mouvement de deuxième ordre ont principalement été effectuées chez le singe et le chat. Chez le chat, toutefois, seules les aires visuelles primaires (17 et 18) ont été extensivement étudiées. L’implication dans le traitement du deuxième ordre de l’aire dédiée à la perception du mouvement, le Sulcus syprasylvien postéro-médian latéral (PMLS), n’est pas encore connue. Pour ce faire, nous avons étudié les profils de réponse des neurones du PMLS évoqués par des stimuli dont la composante dynamique était de deuxième ordre. Les profils de réponses au mouvement de deuxième ordre sont très similaires au premier ordre, bien que moins sensibles. Nos données suggèrent que la perception du mouvement par le PMLS serait de type form-cue invariant. En somme, les résultats démontrent que le PMLS permet un traitement plus complexe du mouvement du deuxième ordre et sont en accord avec son rôle privilégié dans la perception du mouvement.

Évaluation du régulateur sur une courbe modulaire et valeurs particulières

Bloch et Beilinson ont proposé plusieurs conjectures sur les liens entre les applications régulateurs du groupe de K-théorie algébrique associée à une courbe modulaire et des valeurs spéciales de fonction L. Fixons N, un entier naturel et considérons le sous-groupe de congruence $\Gamma_0(N)$. Le présent mémoire démontre une formule explicite entre le régulateur de la courbe modulaire $X_0(N)$ appliqué à une forme primitive et une valeur spéciale de la fonction L associée.

Structures algébriques, systèmes superintégrables et polynômes orthogonaux

Cette thèse est divisée en cinq parties portant sur les thèmes suivants: l’interprétation physique et algébrique de familles de fonctions orthogonales multivariées et leurs applications, les systèmes quantiques superintégrables en deux et trois dimensions faisant intervenir des opérateurs de réflexion, la caractérisation de familles de polynômes orthogonaux appartenant au tableau de Bannai-Ito et l’examen des structures algébriques qui leurs sont associées, l’étude de la relation entre le recouplage de représentations irréductibles d’algèbres et de superalgèbres et les systèmes superintégrables, ainsi que l’interprétation algébrique de familles de polynômes multi-orthogonaux matriciels. Dans la première partie, on développe l’interprétation physico-algébrique des familles de polynômes orthogonaux multivariés de Krawtchouk, de Meixner et de Charlier en tant qu’éléments de matrice des représentations unitaires des groupes SO(d+1), SO(d,1) et E(d) sur les états d’oscillateurs. On détermine les amplitudes de transition entre les états de l’oscillateur singulier associés aux bases cartésienne et polysphérique en termes des polynômes multivariés de Hahn. On examine les coefficients 9j de su(1,1) par le biais du système superintégrable générique sur la 3-sphère. On caractérise les polynômes de q-Krawtchouk comme éléments de matrices des «q-rotations» de U_q(sl_2). On conçoit un réseau de spin bidimensionnel qui permet le transfert parfait d’états quantiques à l’aide des polynômes de Krawtchouk à deux variables et on construit un modèle discret de l’oscillateur quantique dans le plan à l’aide des polynômes de Meixner bivariés. Dans la seconde partie, on étudie les systèmes superintégrables de type Dunkl, qui font intervenir des opérateurs de réflexion. On examine l’oscillateur de Dunkl en deux et trois dimensions, l’oscillateur singulier de Dunkl dans le plan et le système générique sur la 2-sphère avec réflexions. On démontre la superintégrabilité de chacun de ces systèmes. On obtient leurs constantes du mouvement, on détermine leurs algèbres de symétrie et leurs représentations, on donne leurs solutions exactes et on détaille leurs liens avec les polynômes orthogonaux du tableau de Bannai-Ito. Dans la troisième partie, on caractérise deux familles de polynômes du tableau de Bannai-Ito: les polynômes de Bannai-Ito complémentaires et les polynômes de Chihara. On montre également que les polynômes de Bannai-Ito sont les coefficients de Racah de la superalgèbre osp(1,2). On détermine l’algèbre de symétrie des polynômes duaux -1 de Hahn dans le cadre du problème de Clebsch-Gordan de osp(1,2). On propose une q - généralisation des polynômes de Bannai-Ito en examinant le problème de Racah pour la superalgèbre quantique osp_q(1,2). Finalement, on montre que la q -algèbre de Bannai-Ito sert d’algèbre de covariance à osp_q(1,2). Dans la quatrième partie, on détermine le lien entre le recouplage de représentations des algèbres su(1,1) et osp(1,2) et les systèmes superintégrables du deuxième ordre avec ou sans réflexions. On étudie également les représentations des algèbres de Racah-Wilson et de Bannai-Ito. On montre aussi que l’algèbre de Racah-Wilson sert d’algèbre de covariance quadratique à l’algèbre de Lie sl(2). Dans la cinquième partie, on construit deux familles explicites de polynômes d-orthogonaux basées sur su(2). On étudie les états cohérents et comprimés de l’oscillateur fini et on caractérise une famille de polynômes multi-orthogonaux matriciels.

Théorème de Pleijel pour l'oscillateur harmonique quantique

L'objectif de ce mémoire est de démontrer certaines propriétés géométriques des fonctions propres de l'oscillateur harmonique quantique. Nous étudierons les domaines nodaux, c'est-à-dire les composantes connexes du complément de l'ensemble nodal. Supposons que les valeurs propres ont été ordonnées en ordre croissant. Selon un théorème fondamental dû à Courant, une fonction propre associée à la $n$-ième valeur propre ne peut avoir plus de $n$ domaines nodaux. Ce résultat a été prouvé initialement pour le laplacien de Dirichlet sur un domaine borné mais il est aussi vrai pour l'oscillateur harmonique quantique isotrope. Le théorème a été amélioré par Pleijel en 1956 pour le laplacien de Dirichlet. En effet, on peut donner un résultat asymptotique plus fort pour le nombre de domaines nodaux lorsque les valeurs propres tendent vers l'infini. Dans ce mémoire, nous prouvons un résultat du même type pour l'oscillateur harmonique quantique isotrope. Pour ce faire, nous utiliserons une combinaison d'outils classiques de la géométrie spectrale (dont certains ont été utilisés dans la preuve originale de Pleijel) et de plusieurs nouvelles idées, notamment l'application de certaines techniques tirées de la géométrie algébrique et l'étude des domaines nodaux non-bornés.

La synergologie, une lecture pseudoscientifique du langage corporel

L’objectif du présent article est d’évaluer si la synergologie fait partie du domaine de la science ou si elle n’est qu’une pseudoscience du décodage du non-verbal. Le texte comprend cinq parties. Dans la première partie, nous décrivons des éléments importants de la démarche scientifique. Dans les deuxième et troisième parties, nous présentons brièvement la synergologie et nous vérifions si celle-ci respecte les critères de la science. La quatrième partie fait état d’une mise en demeure adressée à Patrick Lagacé et à La Presse pour une série de textes qui présentait une vision très critique de cette approche. Enfin, l’utilisation d’arguments non pertinents d’un point de vue scientifique, une tentative inappropriée de donner de la crédibilité à la synergologie par une mise en demeure et un recours injustifié à l’argument éthique nous amènent à conclure que la synergologie est une pseudoscience du décodage du non-verbal.

A Beacon based Localization System for Autonomous Mobile Robots and its Applications in Traffic and Transport Control

ACCURATE sensing of vehicle position and attitude is still a very challenging problem in many mobile robot applications. The mobile robot vehicle applications must have some means of estimating where they are and in which direction they are heading. Many existing indoor positioning systems are limited in workspace and robustness because they require clear lines-of-sight or do not provide absolute, driftfree measurements.The research work presented in this dissertation provides a new approach to position and attitude sensing system designed specifically to meet the challenges of operation in a realistic, cluttered indoor environment, such as that of an office building, hospital, industrial or warehouse. This is accomplished by an innovative assembly of infrared LED source that restricts the spreading of the light intensity distribution confined to a sheet of light and is encoded with localization and traffic information. This Digital Infrared Sheet of Light Beacon (DISLiB) developed for mobile robot is a high resolution absolute localization system which is simple, fast, accurate and robust, without much of computational burden or significant processing. Most of the available beacon's performance in corridors and narrow passages are not satisfactory, whereas the performance of DISLiB is very encouraging in such situations. This research overcomes most of the inherent limitations of existing systems.The work further examines the odometric localization errors caused by over count readings of an optical encoder based odometric system in a mobile robot due to wheel-slippage and terrain irregularities. A simple and efficient method is investigated and realized using an FPGA for reducing the errors. The detection and correction is based on redundant encoder measurements. The method suggested relies on the fact that the wheel slippage or terrain irregularities cause more count readings from the encoder than what corresponds to the actual distance travelled by the vehicle.The application of encoded Digital Infrared Sheet of Light Beacon (DISLiB) system can be extended to intelligent control of the public transportation system. The system is capable of receiving traffic status input through a GSM (Global System Mobile) modem. The vehicles have infrared receivers and processors capable of decoding the information, and generating the audio and video messages to assist the driver. The thesis further examines the usefulness of the technique to assist the movement of differently-able (blind) persons in indoor or outdoor premises of his residence.The work addressed in this thesis suggests a new way forward in the development of autonomous robotics and guidance systems. However, this work can be easily extended to many other challenging domains, as well.

Bidirectional communication using delay coupled chaotic directly modulated semiconductor lasers

Chaotic synchronization of two directly modulated semiconductor lasers with negative delayed optoelectronic feedback is investigated and this scheme is found to be useful for e±cient bidirectional communication between the lasers. A symmetric bidirec- tional coupling is identified as a suitable method for isochronal synchronization of such lasers. The optimum values of coupling and feedback strength that can provide maxi- mum quality of synchronization are identified. This method is successfully employed for encoding/decoding both analog and digital messages. The importance of a symmetric coupling is demonstrated by studying the variation of decoding efficiency with respect to asymmetric coupling.

Vacancy-assisted domain-growth in asymmetric binary alloys: A Monte Carlo Study

A Monte Carlo simulation study of the vacancy-assisted domain growth in asymmetric binary alloys is presented. The system is modeled using a three-state ABV Hamiltonian which includes an asymmetry term. Our simulated system is a stoichiometric two-dimensional binary alloy with a single vacancy which evolves according to the vacancy-atom exchange mechanism. We obtain that, compared to the symmetric case, the ordering process slows down dramatically. Concerning the asymptotic behavior it is algebraic and characterized by the Allen-Cahn growth exponent x51/2. The late stages of the evolution are preceded by a transient regime strongly affected by both the temperature and the degree of asymmetry of the alloy. The results are discussed and compared to those obtained for the symmetric case.

Studies in molecular mechanics using spectroscopic data exact force field and bond in homogeneity

This thesis deals with some studies in molecular mechanic using spectroscopic data. It includes an improvement in the parameter technique for the evaluation of exact force fields, the introduction of a new and simple algebraic method for the force field calculation and a study of asymmetric variation of bonding forces along a bond.

Some problems in set topology relating group of homeomorphisms and order

In this thesis we investigate some problems in set theoretical topology related to the concepts of the group of homeomorphisms and order. Many problems considered are directly or indirectly related to the concept of the group of homeomorphisms of a topological space onto itself. Order theoretic methods are used extensively. Chapter-l deals with the group of homeomorphisms. This concept has been investigated by several authors for many years from different angles. It was observed that nonhomeomorphic topological spaces can have isomorphic groups of homeomorphisms. Many problems relating the topological properties of a space and the algebraic properties of its group of homeomorphisms were investigated. The group of isomorphisms of several algebraic, geometric, order theoretic and topological structures had also been investigated. A related concept of the semigroup of continuous functions of a topological space also received attention