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.

Structures linéaires dans les ensembles à faible densité

Réalisé en cotutelle avec l'Université Paris-Diderot.

Evaluating DNA damage response (DDR) activation in human prostate cancer

Introduction: Au Canada, le cancer de la prostate est le cancer le plus fréquemment diagnostiqué chez les hommes et le plus mortel après les cancers du poumon et du côlon. Il y a place à optimiser le traitement du cancer de la prostate de manière à mettre en œuvre une médecine personnalisée qui s’adapte aux caractéristiques de la maladie de chaque patient de façon individuelle. Dans ce mémoire, nous avons évalué la réponse aux dommages de l’ADN (RDA) comme biomarqueur potentiel du cancer de la prostate. Les lésions potentiellement oncogènes de l'ADN déclenche une cascade de signalisation favorisant la réparation de l'ADN et l’activation des points de contrôle du cycle cellulaire pour préserver l’intégrité du génome. La RDA est un mécanisme central de suppression tumorale chez l’homme. La RDA joue un rôle important dans l’arrêt de la prolifération des cellules dont les génomes sont compromis, et donc, prévient la progression du cancer en agissant comme une barrière. Cette réponse cellulaire détermine également comment les cellules normales et cancéreuses réagissent aux agents utilisés pour endommager l'ADN lors du traitement du cancer comme la radiothérapie ou la chimiothérapie, en plus la présence d,un certain niveau de RDA dans les cellules du cancer de la prostate peuvent également influer sur l'issue de ces traitements. L’activation des signaux de la RDA peut agir comme un frein au cancer dans plusieurs lésions pré-néoplasiques de l'homme, y compris le cancer de la prostate. Il a été démontré que la RDA est augmentée dans les cellules de néoplasie intra- épithéliale (PIN) comparativement aux cellules prostatiques normales. Toutefois, le devient de la RDA entre le PIN et l’adénocarcinome est encore mal documenté et aucune corrélation n'a été réalisée avec les données cliniques des patients. Notre hypothèse est que les niveaux d’activation de la RDA seront variables selon les différents grades et agressivité du cancer de la prostate. Ces niveaux pourront être corrélés et possiblement prédire les réponses cliniques aux traitements des patients et aider à définir une stratégie plus efficace et de nouveaux biomarqueurs pour prédire les résultats du traitement et personnaliser les traitements en conséquence. Nos objectifs sont de caractériser l'activation de la RDA dans le carcinome de la prostate et corréler ses données avec les résultats cliniques. Méthodes : Nous avons utilisé des micro-étalages de tissus (tissue microarrays- TMAs) de 300 patients ayant subi une prostatectomie radicale pour un cancer de la prostate et déterminé le niveau d’expression de protéines de RDA dans le compartiment stromal et épithélial des tissus normaux et cancéreux. Les niveaux d’expression de 53BP1, p-H2AX, p65 et p-CHK2 ont été quantifiés par immunofluorescence (IF) et par un logiciel automatisé. Ces marqueurs de RDA ont d’abord été validés sur des TMAs-cellule constitués de cellules de fibroblastes normales ou irradiées (pour induire une activation du RDA). Les données ont été quantifiées à l'aide de couches binaires couramment utilisées pour classer les pixels d'une image pour que l’analyse se fasse de manière indépendante permettant la détection de plusieurs régions morphologiques tels que le noyau, l'épithélium et le stroma. Des opérations arithmétiques ont ensuite été réalisées pour obtenir des valeurs correspondant à l'activation de la RDA qui ont ensuite été corrélées à la récidive biochimique et l'apparition de métastases osseuses. Résultats : De faibles niveaux d'expression de la protéine p65 dans le compartiment nucléaire épithélial du tissu normal de la prostate sont associés à un faible risque de récidive biochimique. Par ailleurs, nous avons aussi observé que de faibles niveaux d'expression de la protéine 53BP1 dans le compartiment nucléaire épithéliale du tissu prostatique normal et cancéreux ont été associés à une plus faible incidence de métastases osseuses. Conclusion: Ces résultats confirment que p65 a une valeur pronostique chez les patients présentant un adénocarcinome de la prostate. Ces résultats suggèrent également que le marqueur 53BP1 peut aussi avoir une valeur pronostique chez les patients avec le cancer de la prostate. La validation d'autres marqueurs de RDA pourront également être corrélés aux résultats cliniques. De plus, avec un suivi des patients plus long, il se peut que ces résultats se traduisent par une corrélation avec la survie. Les niveaux d'activité de la RDA pourront éventuellement être utilisés en clinique dans le cadre du profil du patient comme le sont actuellement l’antigène prostatique spécifique (APS) ou le Gleason afin de personnaliser le traitement.

Lien entre l'activité pariéto-occipitale enregistrée pendant une tâche de mémoire à court terme visuelle et les habiletés mathématiques : une étude en magnétoencéphalographie

La mémoire à court terme visuelle (MCTv) est un système qui permet le maintien temporaire de l’information visuelle en mémoire. La capacité en mémoire à court terme se définit par le nombre d’items qu’un individu peut maintenir en mémoire sur une courte période de temps et est limitée à environ quatre items. Il a été démontré que la capacité en MCTv et les habiletés mathématiques sont étroitement liées. La MCTv est utile dans beaucoup de composantes liées aux mathématiques, comme la résolution de problèmes, la visualisation mentale et l’arithmétique. En outre, la MCTv et le raisonnement mathématique font appel à des régions similaires du cerveau, notamment dans le cortex pariétal. Le sillon intrapariétal (SIP) semble être particulièrement important, autant dans la réalisation de tâches liées à la MCTv qu’aux habiletés mathématiques. Nous avons créé une tâche de MCTv que 15 participants adultes en santé ont réalisée pendant que nous enregistrions leur activité cérébrale à l’aide de la magnétoencéphalographie (MEG). Nous nous sommes intéressés principalement à la composante SPCM. Une évaluation neuropsychologique a également été administrée aux participants. Nous souhaitions tester l’hypothèse selon laquelle l’activité cérébrale aux capteurs pariéto-occipitaux pendant la tâche de MCTv en MEG sera liée à la performance en mathématiques. Les résultats indiquent que l’amplitude de l’activité pariéto-occipitale pendant la tâche de MCTv permet de prédire les habiletés mathématiques ainsi que la performance dans une tâche de raisonnement perceptif. Ces résultats permettent de confirmer le lien existant entre les habiletés mathématiques et le fonctionnement sous-jacent à la MCTv.

On Space-Time Trade-Off for Montgomery Multipliers over Finite Fields

La multiplication dans le corps de Galois à 2^m éléments (i.e. GF(2^m)) est une opérations très importante pour les applications de la théorie des correcteurs et de la cryptographie. Dans ce mémoire, nous nous intéressons aux réalisations parallèles de multiplicateurs dans GF(2^m) lorsque ce dernier est généré par des trinômes irréductibles. Notre point de départ est le multiplicateur de Montgomery qui calcule A(x)B(x)x^(-u) efficacement, étant donné A(x), B(x) in GF(2^m) pour u choisi judicieusement. Nous étudions ensuite l'algorithme diviser pour régner PCHS qui permet de partitionner les multiplicandes d'un produit dans GF(2^m) lorsque m est impair. Nous l'appliquons pour la partitionnement de A(x) et de B(x) dans la multiplication de Montgomery A(x)B(x)x^(-u) pour GF(2^m) même si m est pair. Basé sur cette nouvelle approche, nous construisons un multiplicateur dans GF(2^m) généré par des trinôme irréductibles. Une nouvelle astuce de réutilisation des résultats intermédiaires nous permet d'éliminer plusieurs portes XOR redondantes. Les complexités de temps (i.e. le délais) et d'espace (i.e. le nombre de portes logiques) du nouveau multiplicateur sont ensuite analysées: 1. Le nouveau multiplicateur demande environ 25% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito lorsque GF(2^m) est généré par des trinômes irréductible et m est suffisamment grand. Le nombre de portes du nouveau multiplicateur est presque identique à celui du multiplicateur de Karatsuba proposé par Elia. 2. Le délai de calcul du nouveau multiplicateur excède celui des meilleurs multiplicateurs d'au plus deux évaluations de portes XOR. 3. Nous determinons le délai et le nombre de portes logiques du nouveau multiplicateur sur les deux corps de Galois recommandés par le National Institute of Standards and Technology (NIST). Nous montrons que notre multiplicateurs contient 15% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito au coût d'un délai d'au plus une porte XOR supplémentaire. De plus, notre multiplicateur a un délai d'une porte XOR moindre que celui du multiplicateur d'Elia au coût d'une augmentation de moins de 1% du nombre total de portes logiques.

A non reductionist logicism with explicit definitions

This paper introduces and examines the logicist construction of Peano Arithmetic that can be performed into Leśniewski’s logical calculus of names called Ontology. Against neo-Fregeans, it is argued that a logicist program cannot be based on implicit definitions of the mathematical concepts. Using only explicit definitions, the construction to be presented here constitutes a real reduction of arithmetic to Leśniewski’s logic with the addition of an axiom of infinity. I argue however that such a program is not reductionist, for it only provides what I will call a picture of arithmetic, that is to say a specific interpretation of arithmetic in which purely logical entities play the role of natural numbers. The reduction does not show that arithmetic is simply a part of logic. The process is not of ontological significance, for numbers are not shown to be logical entities. This neo-logicist program nevertheless shows the existence of a purely analytical route to the knowledge of arithmetical laws.

Existence of multiple attractors and the nature of bifurcations in a discontinuous logistic map

We present the analytical investigations on a logistic map with a discontinuity at the centre. An explanation for the bifurcation phenomenon in discontinuous systems is presented. We establish that whenever the elements of an n-cycle (n > 1) approach the discontinuities of the nth iterate of the map, a bifurcation other than the usual period-doubling one takes place. The periods of the cycles decrease in an arithmetic progression, as the control parameter is varied. The system also shows the presence of multiple attractors. Our results are verified by numerical experiments as well.

Complexity quantification of dense array EEG using sample entropy analysis

n this paper, a time series complexity analysis of dense array electroencephalogram signals is carried out using the recently introduced Sample Entropy (SampEn) measure. This statistic quantifies the regularity in signals recorded from systems that can vary from the purely deterministic to purely stochastic realm. The present analysis is conducted with an objective of gaining insight into complexity variations related to changing brain dynamics for EEG recorded from the three cases of passive, eyes closed condition, a mental arithmetic task and the same mental task carried out after a physical exertion task. It is observed that the statistic is a robust quantifier of complexity suited for short physiological signals such as the EEG and it points to the specific brain regions that exhibit lowered complexity during the mental task state as compared to a passive, relaxed state. In the case of mental tasks carried out before and after the performance of a physical exercise, the statistic can detect the variations brought in by the intermediate fatigue inducing exercise period. This enhances its utility in detecting subtle changes in the brain state that can find wider scope for applications in EEG based brain studies.

Design and synthesis of efficient mac architectures for high speed decimal processor

Most of the commercial and financial data are stored in decimal fonn. Recently, support for decimal arithmetic has received increased attention due to the growing importance in financial analysis, banking, tax calculation, currency conversion, insurance, telephone billing and accounting. Performing decimal arithmetic with systems that do not support decimal computations may give a result with representation error, conversion error, and/or rounding error. In this world of precision, such errors are no more tolerable. The errors can be eliminated and better accuracy can be achieved if decimal computations are done using Decimal Floating Point (DFP) units. But the floating-point arithmetic units in today's general-purpose microprocessors are based on the binary number system, and the decimal computations are done using binary arithmetic. Only few common decimal numbers can be exactly represented in Binary Floating Point (BF P). ln many; cases, the law requires that results generated from financial calculations performed on a computer should exactly match with manual calculations. Currently many applications involving fractional decimal data perform decimal computations either in software or with a combination of software and hardware. The performance can be dramatically improved by complete hardware DFP units and this leads to the design of processors that include DF P hardware.VLSI implementations using same modular building blocks can decrease system design and manufacturing cost. A multiplexer realization is a natural choice from the viewpoint of cost and speed.This thesis focuses on the design and synthesis of efficient decimal MAC (Multiply ACeumulate) architecture for high speed decimal processors based on IEEE Standard for Floating-point Arithmetic (IEEE 754-2008). The research goal is to design and synthesize deeimal'MAC architectures to achieve higher performance.Efficient design methods and architectures are developed for a high performance DFP MAC unit as part of this research.

On infinite graphs and related matrices

This thesis Entitled On Infinite graphs and related matrices.ln the last two decades (iraph theory has captured wide attraction as a Mathematical model for any system involving a binary relation. The theory is intimately related to many other branches of Mathematics including Matrix Theory Group theory. Probability. Topology and Combinatorics . and has applications in many other disciplines..Any sort of study on infinite graphs naturally involves an attempt to extend the well known results on the much familiar finite graphs. A graph is completely determined by either its adjacencies or its incidences. A matrix can convey this information completely. This makes a proper labelling of the vertices. edges and any other elements considered, an inevitable process. Many types of labelling of finite graphs as Cordial labelling, Egyptian labelling, Arithmetic labeling and Magical labelling are available in the literature. The number of matrices associated with a finite graph are too many For a study ofthis type to be exhaustive. A large number of theorems have been established by various authors for finite matrices. The extension of these results to infinite matrices associated with infinite graphs is neither obvious nor always possible due to convergence problems. In this thesis our attempt is to obtain theorems of a similar nature on infinite graphs and infinite matrices. We consider the three most commonly used matrices or operators, namely, the adjacency matrix

A study on fuzzy semi inner product spaces

Mathematical models are often used to describe physical realities. However, the physical realities are imprecise while the mathematical concepts are required to be precise and perfect. The 1st chapter give a brief summary of the arithmetic of fuzzy real numbers and the fuzzy normed algebra M(I). Also we explain a few preliminary definitions and results required in the later chapters. Fuzzy real numbers are introduced by Hutton,B [HU] and Rodabaugh, S.E[ROD]. Our definition slightly differs from this with an additional minor restriction. The definition of Clementina Felbin [CL1] is entirely different. The notations of [HU]and [M;Y] are retained inspite of the slight difference in the concept.the 3rd chapter In this chapter using the completion M'(I) of M(I) we give a fuzzy extension of real Hahn-Banch theorem. Some consequences of this extension are obtained. The idea of real fuzzy linear functional on fuzzy normed linear space is introduced. Some of its properties are studied. In the complex case we get only a slightly weaker analogue for the Hahn-Banch theorem, than the one [B;N] in the crisp case

A new look at reversible logic implementation of decimal adder

Reversibility plays a fundamental role when logic gates such as AND, OR, and XOR are not reversible. computations with minimal energy dissipation are considered. Hence, these gates dissipate heat and may reduce the life of In recent years, reversible logic has emerged as one of the most the circuit. So, reversible logic is in demand in power aware important approaches for power optimization with its circuits. application in low power CMOS, quantum computing and A reversible conventional BCD adder was proposed in using conventional reversible gates.

Quick Addition of Decimals Using Reversible Conservative Logic

In recent years, reversible logic has emerged as one of the most important approaches for power optimization with its application in low power CMOS, nanotechnology and quantum computing. This research proposes quick addition of decimals (QAD) suitable for multi-digit BCD addition, using reversible conservative logic. The design makes use of reversible fault tolerant Fredkin gates only. The implementation strategy is to reduce the number of levels of delay there by increasing the speed, which is the most important factor for high speed circuits.

Performance Analysis of Reversible Fast Decimal Adders

This paper presents a performance analysis of reversible, fault tolerant VLSI implementations of carry select and hybrid decimal adders suitable for multi-digit BCD addition. The designs enable partial parallel processing of all digits that perform high-speed addition in decimal domain. When the number of digits is more than 25 the hybrid decimal adder can operate 5 times faster than conventional decimal adder using classical logic gates. The speed up factor of hybrid adder increases above 10 when the number of decimal digits is more than 25 for reversible logic implementation. Such highspeed decimal adders find applications in real time processors and internet-based applications. The implementations use only reversible conservative Fredkin gates, which make it suitable for VLSI circuits.

Die aeroelastische Stabilitätsanalyse – ein praxisnaher Ansatz zur intervalltheoretischen Betrachtung von Modellierungsunsicherheiten am Flugzeug

Die Untersuchung des dynamischen aeroelastischen Stabilitätsverhaltens von Flugzeugen erfordert sehr komplexe Rechenmodelle, welche die wesentlichen elastomechanischen und instationären aerodynamischen Eigenschaften der Konstruktion wiedergeben sollen. Bei der Modellbildung müssen einerseits Vereinfachungen und Idealisierungen im Rahmen der Anwendung der Finite Elemente Methode und der aerodynamischen Theorie vorgenommen werden, deren Auswirkungen auf das Simulationsergebnis zu bewerten sind. Andererseits können die strukturdynamischen Kenngrößen durch den Standschwingungsversuch identifiziert werden, wobei die Ergebnisse Messungenauigkeiten enthalten. Für eine robuste Flatteruntersuchung müssen die identifizierten Unwägbarkeiten in allen Prozessschritten über die Festlegung von unteren und oberen Schranken konservativ ermittelt werden, um für alle Flugzustände eine ausreichende Flatterstabilität sicherzustellen. Zu diesem Zweck wird in der vorliegenden Arbeit ein Rechenverfahren entwickelt, welches die klassische Flatteranalyse mit den Methoden der Fuzzy- und Intervallarithmetik verbindet. Dabei werden die Flatterbewegungsgleichungen als parameterabhängiges nichtlineares Eigenwertproblem formuliert. Die Änderung der komplexen Eigenlösung infolge eines veränderlichen Einflussparameters wird mit der Methode der numerischen Fortsetzung ausgehend von der nominalen Startlösung verfolgt. Ein modifizierter Newton-Iterations-Algorithmus kommt zur Anwendung. Als Ergebnis liegen die berechneten aeroelastischen Dämpfungs- und Frequenzverläufe in Abhängigkeit von der Fluggeschwindigkeit mit Unschärfebändern vor.