Many developers today have difficulties testing their applications on mobile devices. This is due to a number of factors, such as the fact that the mobile phone market has become even more fragmented with the introduction of touch screen technology. Existing software that was designed for traditional mobile handhelds is not necessarily compatible with the newest models and vice versa. For developers this incompatibility increases the difficulty when creating software. Lack of resources for testing the application may lead to the application being limited to either just a specific model or in some cases to only one specific version of the operating system software. Without providing support for a large number of models the product may have difficulty attracting customers, and hence fail to gain the desired market share. The challenge is to find a way to make testing simple, effective, and automated on a large number of mobile devices. To achieve this test automation applicationsare needed and a test strategy must be devised. Additionally, testing is often described as never-ending since testing generally reveals errors rather than demonstrating when errors are absent. Because of this some limitations of testing are justified. In order to limit the scope of this thesis I have selected some of the most appropriate methods for testing, and will only examine these specific methods.  The focus for the testing is not specifically to find errors, but rather to confirm that the product offers the specified functionality. This thesis describes an approach to functional testing of an application for Symbian mobile devices based upon log analysis. Unfortunately, testing applications on mobile devices is still not straightforward, and this thesis does not shed any light upon how to lessen this complexity. However, I believe that both testing and development will be more and more built around use cases in the future. Unfortunately, automation of testing based uponthese use cases will be further complicated by the increasing use of touch screens and physical input (such as gestures). / Idag har många utvecklare problem med att testa sina applikationer på mobila enheter.Detta har många orsaker, exempelvis att den globala mobila marknaden har blivit än mer fragmenterad i och med introduktionen av pekskärmstekniken och de snabba förändringar som sker idag. På grund av de många telefoner som idag finns så finns det ett behov för en automatiserad testprocess då det tar för lång tid att göra manuellt. OptiCall Solutions AB har utvecklat en applikation för Symbian S60 som behöver kunna köra på många olika telefoner. Denna masteruppsats har målet att hitta ett sätt att automatisera testning av mobilapplikationer på olika enheter, mer specifikt enheter som kör Symbian S60.  OptiCaller är målet för testerna. Testmetodologier och verktyg har analyserats och kraven har samlats in på den önskade lösningen. Lösningen består av ett program som kör testskripten direkt på telefonen, mjukvara som analyserar testresultaten och presenterar dem i ett GUI, ett teststrategidokument, samt ett felrapporteringssystem. Med hjälp av dess kan testaren skapa sina egna skript för att automatisera och sedan samla in resultaten för analys. Detta eliminerar behovet för manuell testning och gör testningen effektivare, speciellt när man kör många tester. Analysmjukvaran är även integrerad med Felrapporteringssystemet för att underlätta felrapportering.

Les travaux de cette thèse s'inscrivent dans la théorie des automates et des langages formels. ils peuvent se diviser en deux parties qui donnent également deux visions différentes de manipuler les langages dans la théorie des automates. La première partie s'intéresse à la notion de dérivation des expressions qui permet de faire passer le formalisme des quotients de langages au niveau des expressions rationnelles. en particulier cette thèse étudie les termes dérivés cassés d'une expression rationnelle. ces termes dérivés cassés permettent, sous certaines circonstances, et à l'aide d'autres opérations, une réversibilité de la transformation d'un automate en une expression rationnelle. Dans la seconde partie, la théorie des automates est utilisée pour traiter des problèmes sur les systèmes de numération. les systèmes de numération représentent des nombres par des mots. il est possible d'utiliser des automates et des transducteurs afin d'être capable de 'compter' sur un langage rationnel représentant les entiers. plus précisément ces automates sont étudiés pour le cas des systèmes de numération abstraits qui associent à chaque entier un mot d'un langage rationnel, ordonné par l'ordre radiciel. dans un tel système, la fonction qui permet de calculer le mot suivant est une fonction co-séquentielle par morceaux, c'est-à-dire qu'il suffit de lire deux fois le mot d'entrée de la droite vers la gauche pour qu'une machine calcule son image. / The works in this thesis lies in the automata and formal languages theory. in the first part, the notion of derivation of rational expressions is studied. more precisely the broken derived terms of a rational expressions. Theses broken derived terms allow, under certain circumstances, with some other operations on automata, to have the reversibility of the transformation of an automaton into a rational expression. In the second part, automata and tranducers allow to 'count' on a numeration system, where integers are represented by words on a rational language. more precisely, this part adress the problem of counting in an abstract numeration systems, which maps to any word of a rational language, ordored by radix order, the integer corresponding to the order of the word. in such a numeration system, the function which computes the successor of a word is a piecewise co-sequential function: it can be realised by a machine which reads the input two times to give the output.

In past years many industries have utilized simulation as a means for decision making. That wave has introduced simulation as a powerful optimization and development tool in the manufacturing industry. Input data collection is a significant and complex event in the process of simulation. The simulation professionals have grown to accept it is as a strenuous but necessary task. Due to the nature of this task, data collection problems are numerous and vary depending on the situation. These problems may involve time consumption, lack of data, lack of structure, etc. This study concentrates on the challenges of input data collection for Discrete Event Simulation in the manufacturing industry and focuses particularly on speed, efficiency, data completeness and data accuracy. It has been observed that many companies have recently utilized commercial databases to store production data. This study proposes that the key to faster and more efficient input data collection is to extract data directly from these sources in a flexible and efficient way. An approach is introduced here to creating a custom software tool for a manufacturing setting that allows input data to be collected and formatted quickly and accurately. The methodology for the development of such a custom tool and its implementation, Part Data Collection, are laid out in this research. The Part Data Collection application was developed to assist in the simulation endeavors of Lockheed Martin Missiles and Fire Control in Orlando, Florida. It was implemented and tested as an aid in a large simulation project, which included modeling a new factory. This implementation resulted in 93% reduction in labor time associated with data collection and significantly improved data accuracy.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La recherche de solutions analytiques pour l’évaluation de la fiabilité en contexte dynamique n’est pas résolue dans le cas général. Un état de l’art présenté dans le chapitre 1 montre que des approches partielles relatives à des hypothèses particulières existent. La simulation de Monte Carlo serait le seul recours, mais il n’existait pas d’outils performants permettant la simulation simultanée de l’évolution discrète du système et de son évolution continue prenant en compte les aspects probabilistes. Dans ce contexte, dans le chapitre 2, nous introduisons le concept d’automate stochastique hybride capable de prendre en compte tous les problèmes posés par la fiabilité dynamique et d’accéder à l’évaluation des grandeurs de la sûreté de fonctionnement par une simulation de Monte Carlo implémentée dans l’environnement Scilab-Scicos. Dans le chapitre 3, nous montrons l’efficacité de notre approche de simulation pour l’évaluation de la sûreté de fonctionnement en contexte dynamique sur deux cas test dont un est un benchmark de la communauté de la Sûreté de Fonctionnement. Notre approche permet de répondre aux problèmes posés, notamment celui de la prise en compte de l’influence de l’état discret, de l’état continu et de leur interaction dans l’évaluation probabiliste des performances d’un système dans lequel en outre, les caractéristiques fiabilistes des composants dépendent eux-mêmes des états continu et discret. Dans le chapitre 4, nous donnons une idée de l’intérêt du contrôle par supervision comme moyen de la sûreté de fonctionnement. Les concepts d’automate observateur et de contrôleur ont été introduits et illustrés sur notre cas test afin de montrer leur potentialité / The research of analytical solutions for reliability assessment in dynamic context is not solved in the general case. A state of the art presented in chapter 1 shows that partial approaches exist in the case of particular hypothesis. The Monte Carlo simulation would be the only recourse, but there were no tools allowing the simultaneous simulation of the discrete evolution of the system and its continuous evolution taking into account the probabilistic aspects. In this context, in chapter 2, we introduce the concept of hybrid stochastic automaton capable of taking into account all the problems posed by dynamic reliability and to accede to the assessment of dependability parameters by a Monte Carlo simulation implemented in Scicos-Scilab environment. In chapter 3, we show the effectiveness of our approach of simulation for dependability assessment in dynamic context through two test cases of which case one is a benchmark of dependability community. Our approach responds to the posed problems, notably the consideration of the influence of the discrete state, of the continuous state and their interaction, in the probabilistic assessment of the performances of a system in which besides, the reliability characteristics of components depend themselves of the continuous and discrete states. In chapter 4, we give an idea of the interest of control by supervision as a means of dependability. The concepts of observer automaton and of controller have been introduced and illustrated on our test case in order to show their potential

Le concept d'automate cellulaire quantique (QCA) introduit en 1993 représente un changement de paradigme dans la microélectronique moderne. Introduite en 1993, cette technologie utilise la position de quelques électrons plutôt que la quantité d'électrons dans un condensateur pour encoder l'information. Ce paradigme réduit grandement la consommation énergétique de ces dispositifs électroniques et pourrait permettre de repousser les limites rencontrées avec les technologies classiques. Plusieurs réalisations expérimentales de ce concept ont été réalisées, mais ne fonctionnent qu'à très basse température (1,5 K). Les développements réalisés à l'aide du procédé nanodamascène à l'Université de Sherbrooke ont permis de démontrer la faisabilité de fabrication des transistors monoélectroniques fonctionnant à haute température (> 400 K). Ces transistors sont sensibles à des variations de la configuration de charges plus faible que la charge d'un électron et peuvent donc servir de détecteurs de charge. Cette fonctionnalité en fait un outil indispensable pour la détection de l'état de sortie d'un circuit QCA. Les travaux de cette thèse portent sur la combinaison de ces deux technologies avec l'objectif de pouvoir élever la température d'opération des QCA électrostatiques. L'architecture d'une demi-cellule QCA bistable pour l'encodage de l'information binaire et des transistors monoélectroniques comme détecteurs de l'état de charge de la demi-cellule est conçue afin de fabriquer ces deux parties en utilisant le procédé nanodamascène. À terme, la combinaison des deux concepts pourrait donner une technologie compatible avec les technologies actuelles et fonctionnant à haute température. Le document présente une méthode de simulation innovante permettant d'utiliser la géométrie réelle du dispositif et d'obtenir les caractéristiques électriques en tenant compte des effets parasites. Cette méthode est utilisée pour optimiser le dessin du dispositif, pour corréler les résultats attendus avec les mesures expérimentales, puis pour en extraire certains paramètres comme les résistances tunnel et les permittivités diélectriques des matériaux de barrière tunnel. Une étude démontrant l'impact de l'utilisation de structures sacrificielles pour le polissage mécano chimique a permis d'optimiser leur taille et leur densité pour améliorer l'uniformité du polissage. Les résultats obtenus de jonctions tunnel MIM ont permis d'améliorer la stabilité dans le temps des dispositifs. Finalement, les caractérisations de transistors monoélectroniques individuels et couplés permettent de démontrer le fonctionnement des dispositifs, leur correspondance aux valeurs attendues et la possibilité de les utiliser comme détecteur de charge. Les résultats présentés dans ces travaux permettent de conclure que tous les éléments nécessaires sont en place pour permettre la fabrication d'une cellule QCA en procédé nanodamascène. Les travaux représentent un premier grand pas vers la démonstration de QCA nanodamascène fonctionnant à haute température.

La thèse s'intéresse au problème de l'analyse syntaxique pour les langages de programmation. Si ce sujet a déjà été traité à maintes reprises, et bien que des outils performants pour la génération d'analyseurs syntaxiques existent et soient largement employés, l'implémentation de la partie frontale d'un compilateur reste encore extrêmement complexe.<br /><br />Ainsi, si le texte d'un programme informatique se doit de n'avoir qu'une seule interprétation possible, l'analyse des langages de programmation, fondée sur une grammaire algébrique, est, pour sa part, le plus souvent non déterministe, voire ambiguë. Confrontés aux insuffisances des analyseurs déterministes traditionnels, les développeurs de parties frontales se sont tournés massivement vers des techniques d'analyse générale, à même d'explorer des choix non déterministes, mais aussi au prix de la garantie d'avoir bien traité toutes les ambiguïtés grammaticales. Une difficulté majeure dans l'implémentation d'un compilateur réside alors dans l'identification (non décidable en général) et le traitement de ces ambiguïtés.<br /><br />Les techniques décrites dans la thèse s'articulent autour d'approximations des grammaires à deux fins. L'une est la génération d'a\-na\-ly\-seurs syntaxiques non canoniques, qui sont moins sensibles aux dif\-fi\-cultés grammaticales, en particulier parce qu'ils peuvent exploiter un langage algébrique non fini en guise de contexte droit pour résoudre un choix non déterministe. Ces analyseurs rétablissent la garantie de non ambiguïté de la grammaire, et en sus assurent un traitement en temps linéaire du texte à analyser. L'autre est la détection d'ambiguïté en tant que telle, avec l'assurance qu'une grammaire acceptée est bien non ambiguë quel que soit le degré d'approximation employé.

Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l’algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck / Pas de résumé en anglais

Ce travail étudie les déviations de sommes ergodiques pour des systèmes dynamiques substitutifs avec une matrice qui admet des valeurs propres de module supérieur à 1. Précisément, nous nous concentrons sur les substitutions telle que ces valeurs propres ne sont pas conjuguées. Dans un premier temps, on défini les lettres a-minimales et dominantes d'un mot pour étudier sa ligne brisée associé. On défini la ligne brisée normalisée et sa fonction limite. Pour l'étude des sommes ergodiques, on défini le sous-automate des lettres minimales. On donne des conditions sur une substitution de sorte qu'il y ait un nombre infini des sommes ergodiques égales à zéro pour un point x 2 X. Enfin, en utilisant un boucle dans une classe de Rauzy, on prouve l'existence d'un nombre infini d'échanges d'intervalles auto-similaires, dont la matrice de Rauzy a deux valeurs propres non conjuguées de module supérieur à 1. Et tout échange d'intervalles affine semi-conjugué à cet échange d'intervalles est aussi conjugué. / This thesis focuses on the deviation of ergodic sums for a substitution dynamical systems with a matrix that admits eigenvalues of modulus larger than 1. Specifically, we concentrate on substitutions with non-conjugated eigenvalues. At first, we define the a-minimals letters and the dominant letters of a word to study its broken associated line. We define the normalize broken line and its limit function. For the study of ergodic sums, we define the sub-automaton of minimum letters. We give conditions on a substitution so that there is infinitely many zero sums ergodic for a point x 2 X. Finally, using a loop in a class of Rauzy, we prove the existence of infinitely many interval exchange transformation self-similar, whose Rauzy matrix has two non-conjugated eigenvalues larger than 1 and every affine interval exchange transformation that is semi-conjugated, is also conjugated.

Les systèmes informatiques jouent un rôle essentiel dans la vie actuelle, et leurs erreurs peuvent avoir des conséquences dramatiques. Il existe des méthodes formelles permettant d'assurer qu'un système informatique est fiable. La méthode formelle utilisée dans cette thèse est appelée complétion d'automates d'arbres et permet d'analyser les systèmes à nombre d'états infini. Dans cette représentation, les états du système sont représentés par des termes et les ensembles d'états par des automates d'arbres. L'ensemble des comportements possibles d'un système est calculé grâce à l'application successive d'un système de réécriture modélisant le comportement du système vérifié. On garantit la fiabilité d'un système en vérifiant qu'un comportement interdit n'est pas présent dans l'ensemble des états accessibles. Mais cet ensemble n'est pas toujours calculable, et nous devons alors calculer une sur-approximation calculable de cet ensemble. Mais cette approximation peut s'avérer trop grossière et reconnaître de faux contre-exemples. La première contribution de cette thèse consiste alors à caractériser, par des formules logiques et de manière automatique, ce qu'est une "bonne" sur-approximation : une approximation représentant un sur-ensemble des configurations accessibles, et qui soit suffisamment précise pour ne pas reconnaître de faux contre-exemples. Résoudre ces formules conduit alors automatiquement à une sur-approximation concluante si elle existe, sans avoir recours à aucun paramétrage manuel. Le second problème de la complétion d'automates d'arbres est le passage à l'échelle, autrement dit le temps de calcul parfois élevé du calcul de complétion quand on s'attaque à des problèmes de la vie courante. Dans la vérification de programmes Java utilisant la complétion d'automates d'arbres, cette explosion peut être due à l'utilisation d'entiers de Peano. L'idée de notre seconde contribution est alors d'évaluer directement le résultat d'une opération arithmétique. D'une façon plus générale, il s'agit d'intégrer les éléments d'un domaine infini dans un automate d'arbres. En s'inspirant de méthodes issues de l'interprétation abstraite, cette thèse intègre des treillis abstraits dans les automates d'arbres, constituant alors un nouveau type d'automates. Les opérations sur le domaine infini représenté sont calculées en une seule étape d'évaluation plutôt que d'appliquer de nombreuses règles de réécriture. Nous avons alors adapté la complétion d'automates d'arbres à ce nouveau type d'automate, et la généricité du nouvel algorithme permet de brancher de nombreux treillis abstraits. Cette technique a été implémentée dans un outil appelé TimbukLTA, et cette implémentation permet de démontrer l'efficacité de cette technique. / Computer systems are more and more important in everyday life, and errors into those systems can make dramatic damages. There are formal methods which can assure reliability of a system. The formal method used in this thesis is called tree automata completion and allows to analyze infinite state systems. In this representation, states of a system are represented by a term and sets of states by tree automata. The set of all reachable behaviors (or states) of the system is computed thanks to successive applications of a term rewriting system which represents the behavior of the system. The reliability of the system is assured by checking that no forbidden state is reachable by the system. But the set of reachable states is not always computable and we need to compute an over-approximation of it. This over-approximation is not always fine enough and can recognize counter examples. The first contribution of this thesis consist in characterizing by logical formulae, in an automatic way, what is a good approximation: an over-approximation which does not contain any counter example. Solving these formulae leads automatically to a good over-approximation if such an approximation exists, without any manual setting. An other problem of tree automata completion is the scaling when dealing with real life problems. In verification of Java programs using tree automata completion, this explosion may be due to the use of Peano numbers. The idea of the second contribution of this thesis is to evaluate directly the result of an arithmetic operation. Generally speaking, we integrate elements of an infinite domain in a tree automaton. Based on abstract interpretation, this thesis allows to integrate abstract lattice in tree automata. Operations on infinite domain are computed in one step of evaluation instead of probably many application of rewrite rules. Thus we adapted tree automata completion to this new type of tree automata with lattice, and genericity of the new algorithm allows to integrate many types of lattices. This technique has been implemented in a tool named TimbukLTA, and this implementation shows the efficiency of the technique.