Nous nous intéressons à la représentation de graphes dans le prouveur Coq. Nous avons choisi de les représenter par des types coinductifs dont nous voulions explorer l'utilisation. Ceux-ci permettent de rendre succincte et élégante la représentation et d'obtenir la navigabilité par construction. Nous avons dû contourner la condition de garde dont le but est d'assurer la validité des opérations effectuées sur les objets coinductifs. Son implantation dans Coq est restrictive et interdit parfois des définitions sémantiquement correctes. Une formalisation canonique des graphes dépasse ainsi l'expressivité directe de Coq. Nous avons donc proposé une solution respectant ces limitations, puis nous avons défini une relation sur les graphes nous permettant d'obtenir la même notion d'équivalence qu'avec une représentation classique tout en gardant les avantages de la coinduction. Nous montrons qu'elle est équivalente à une relation basée sur des observations finies.

Formal methods provide means for rigorously specifying the desired behaviour of a hardware or software system, making a precise model of its actual behaviour, and then verifying whether that actual behaviour corresponds to the specification.<br><br> My habiliation thesis reports on various contributions to this realm, where my main interest has been on algorithmic aspects. This is motivated by the observation that asymptotic worst-case complexity, often used to characterize the difficulty of algorithmic problems, is only loosely related to the difficulty encountered in solving those problems in practice.<br><br> The two main types of system I have been working on are pushdown systems and Petri nets. Both are fundamental notions of computation, and both offer, in my opinion, particularly nice opportunities for combining theory and algorithmics.<br><br> Pushdown systems are finite automata equipped with a stack; since the height of the stack is not bounded, they represent a class of infinite-state systems that model programs with (recursive) procedure calls. Moreover, we shall see that specifying authorizations is another, particularly interesting application of pushdown systems.<br><br> While pushdown systems are primarily suited to express sequential systems, Petri nets model concurrent systems. My contributions in this area all concern unfoldings. In a nutshell, the unfolding of a net N is an acyclic version of N in which loops have been unrolled. Certain verification problems, such as reachability, have a lower complexity on unfoldings than on general Petri nets.

Uma das características mais importantes em Sistemas de Ensino via Web é a tarefa Avaliação. Algumas de suas funções são verificar o quão e quanto o aluno aprendeu e fornecer feedback para o aluno e professor. Neste contexto, este trabalho apresenta EASy, sistema de geração automática de avaliações via Web, proposto para ser integrado ao XHA, ambiente de ensino via Web baseado em Autômatos Finitos com Saída. EASy aplica o mesmo modelo estrutural do XHA, capitalizando as vantagens apresentadas neste modelo para Avaliações. O foco principal deste sistema está na autoria de questões, visando geração automática de Avaliações a partir de metadados configuráveis. Este sistema contempla também os aspectos pedagógicos da avaliação, recursos adaptativos e feedback. Este trabalho tem como propósito apresentar melhorias no processo avaliativo através de um sistema flexível, visando a disponibilidade via Web, onde o acesso do sistema independe da localização por parte do professor. Assim, propõe-se um processo de autoria que possibilite a redução do esforço gasto pelo professor na implementação das questões e na geração dos instrumentos de avaliação. O EASy apresenta também a geração de relatórios detalhados sobre os resultados das avaliações realizadas pelos alunos, possibilitando que o professor empregue mais tempo no acompanhamento do desempenho dos alunos nas avaliações. / The Evaluation task is one of the most important characteristics of a Web learning environment. Verifying how much the student has learned and supplying feedback to the student and to the teacher are some of its functions. In this context, this work presents EASy, a Web-based system for students evaluation, which is designed to be integrated into the existing XHA system, a Web education environment based on Finite Automata with Output. EASy is based on XHA’s structural model, optimizing the advantages presented in this model for Evaluations. This system’s main focus is question authoring, and automatic generation of evaluations from configurable sets of questions metadata. This system also contemplates the pedagogical aspects of the evaluation, adaptive resources and feedback. This work intends to present improvements in the evaluation process by a flexible system, available over the Web, where the access of the teacher to the system is independent of geographical positions. Then we consider an authorship process that makes possible the reduction of efforts by the teacher in the implementation of evaluations questions and generation of the evaluation instruments. The EASy also presents the generation of detailed reports about the results of the evaluations carried through by students, making possible that the teacher may have useful time monitoring the performance of the students in the evaluations.

Uma das características mais importantes em Sistemas de Ensino via Web é a tarefa Avaliação. Algumas de suas funções são verificar o quão e quanto o aluno aprendeu e fornecer feedback para o aluno e professor. Neste contexto, este trabalho apresenta EASy, sistema de geração automática de avaliações via Web, proposto para ser integrado ao XHA, ambiente de ensino via Web baseado em Autômatos Finitos com Saída. EASy aplica o mesmo modelo estrutural do XHA, capitalizando as vantagens apresentadas neste modelo para Avaliações. O foco principal deste sistema está na autoria de questões, visando geração automática de Avaliações a partir de metadados configuráveis. Este sistema contempla também os aspectos pedagógicos da avaliação, recursos adaptativos e feedback. Este trabalho tem como propósito apresentar melhorias no processo avaliativo através de um sistema flexível, visando a disponibilidade via Web, onde o acesso do sistema independe da localização por parte do professor. Assim, propõe-se um processo de autoria que possibilite a redução do esforço gasto pelo professor na implementação das questões e na geração dos instrumentos de avaliação. O EASy apresenta também a geração de relatórios detalhados sobre os resultados das avaliações realizadas pelos alunos, possibilitando que o professor empregue mais tempo no acompanhamento do desempenho dos alunos nas avaliações. / The Evaluation task is one of the most important characteristics of a Web learning environment. Verifying how much the student has learned and supplying feedback to the student and to the teacher are some of its functions. In this context, this work presents EASy, a Web-based system for students evaluation, which is designed to be integrated into the existing XHA system, a Web education environment based on Finite Automata with Output. EASy is based on XHA’s structural model, optimizing the advantages presented in this model for Evaluations. This system’s main focus is question authoring, and automatic generation of evaluations from configurable sets of questions metadata. This system also contemplates the pedagogical aspects of the evaluation, adaptive resources and feedback. This work intends to present improvements in the evaluation process by a flexible system, available over the Web, where the access of the teacher to the system is independent of geographical positions. Then we consider an authorship process that makes possible the reduction of efforts by the teacher in the implementation of evaluations questions and generation of the evaluation instruments. The EASy also presents the generation of detailed reports about the results of the evaluations carried through by students, making possible that the teacher may have useful time monitoring the performance of the students in the evaluations.

In this thesis, we explore the interface between symbolic and dynamical system computation, with particular regard to dynamical system models of neuronal networks. In doing so, we adhere to a definition of computation as the physical realization of a formal system, where we say that a dynamical system performs a computation if a correspondence can be found between its dynamics on a vectorial space and the formal system’s dynamics on a symbolic space. Guided by this definition, we characterize computation in a range of neuronal network models. We first present a constructive mapping between a range of formal systems and Recurrent Neural Networks (RNNs), through the introduction of a Versatile Shift and a modular network architecture supporting its real-time simulation. We then move on to more detailed models of neural dynamics, characterizing the computation performed by networks of delay-pulse-coupled oscillators supporting the emergence of heteroclinic dynamics. We show that a correspondence can be found between these networks and Finite-State Transducers, and use the derived abstraction to investigate how noise affects computation in this class of systems, unveiling a surprising facilitatory effect on information transmission. Finally, we present a new dynamical framework for computation in neuronal networks based on the slow-fast dynamics paradigm, and discuss the consequences of our results for future work, specifically for what concerns the fields of interactive computation and Artificial Intelligence.

Uma das características mais importantes em Sistemas de Ensino via Web é a tarefa Avaliação. Algumas de suas funções são verificar o quão e quanto o aluno aprendeu e fornecer feedback para o aluno e professor. Neste contexto, este trabalho apresenta EASy, sistema de geração automática de avaliações via Web, proposto para ser integrado ao XHA, ambiente de ensino via Web baseado em Autômatos Finitos com Saída. EASy aplica o mesmo modelo estrutural do XHA, capitalizando as vantagens apresentadas neste modelo para Avaliações. O foco principal deste sistema está na autoria de questões, visando geração automática de Avaliações a partir de metadados configuráveis. Este sistema contempla também os aspectos pedagógicos da avaliação, recursos adaptativos e feedback. Este trabalho tem como propósito apresentar melhorias no processo avaliativo através de um sistema flexível, visando a disponibilidade via Web, onde o acesso do sistema independe da localização por parte do professor. Assim, propõe-se um processo de autoria que possibilite a redução do esforço gasto pelo professor na implementação das questões e na geração dos instrumentos de avaliação. O EASy apresenta também a geração de relatórios detalhados sobre os resultados das avaliações realizadas pelos alunos, possibilitando que o professor empregue mais tempo no acompanhamento do desempenho dos alunos nas avaliações. / The Evaluation task is one of the most important characteristics of a Web learning environment. Verifying how much the student has learned and supplying feedback to the student and to the teacher are some of its functions. In this context, this work presents EASy, a Web-based system for students evaluation, which is designed to be integrated into the existing XHA system, a Web education environment based on Finite Automata with Output. EASy is based on XHA’s structural model, optimizing the advantages presented in this model for Evaluations. This system’s main focus is question authoring, and automatic generation of evaluations from configurable sets of questions metadata. This system also contemplates the pedagogical aspects of the evaluation, adaptive resources and feedback. This work intends to present improvements in the evaluation process by a flexible system, available over the Web, where the access of the teacher to the system is independent of geographical positions. Then we consider an authorship process that makes possible the reduction of efforts by the teacher in the implementation of evaluations questions and generation of the evaluation instruments. The EASy also presents the generation of detailed reports about the results of the evaluations carried through by students, making possible that the teacher may have useful time monitoring the performance of the students in the evaluations.

What do you do if a computational object fails a specification? An obvious approach is to repair it, namely, to modify the object minimally to get something that satisfies the constraints. In this thesis we study foundational problems of repairing regular specifications over strings and trees. Given two regular specifications R and T we aim to understand how difficult it is to transform an object satisfying R into an object satisfying T. The setting is motivated by considering R to be a restriction -- a constraint that the input object is guaranteed to satisfy -- while T is a target -- a constraint that we want to enforce. We first study which pairs of restriction and target specifications can be repaired with a ``small'' numbers of changes. We formalize this as the bounded repair problem -- to determine whether one can repair each object satisfying R into T with a uniform number of edits. We provide effective characterizations of the bounded repair problem for regular specifications over strings and trees. These characterizations are based on a good understanding of the cyclic behaviour of finite automata. By exploiting these characterizations, we give optimal algorithms to decide whether two specifications are bounded repairable or not. We also consider the impact of limitations on the editing process -- what happens when we require the repair to be done sequentially over serialized objects. We study the bounded repair problem over strings and trees restricted to this streaming setting and show that this variant can be characterized in terms of finite games. Furthermore, we use this characterization to decide whether one can repair a pair of specifications in a streaming fashion with bounded cost and how to obtain a streaming repair strategy in this case. The previous notion asks for a uniform bound on the number of edits, but having this property is a strong requirement. To overcome this limitation, we study how to calculate the maximum number of edits per character needed to repair any object in R into T. We formalize this as the asymptotic cost -- the limit of the number of edits divided by the length of the input in the worst case. Our contribution is an algorithm to compute the asymptotic cost for any pair of regular specifications over strings. We also consider the streaming variant of this cost and we show how to compute it by reducing this problem to mean-payoff games.

Les travaux développés dans cette thèse empruntent trois directions principales. D'une part, une étude attentive des propriétés de l'automate universel d'un langage rationnel a été menée. Cet automate fini (introduit sous une forme sensiblement différente par J.H. Conway) accepte le langage et a la particularité de contenir l'image par morphisme de n'importe quel automate équivalent. Nous donnons un algorithme pour le construire à partir de l'automate minimal. L'exploitation des propriétés de l'automate universel d'un langage réversible nous a permis de montrer qu'il existe un sous-automate quasi-réversible (à partir duquel on peut facilement construire un automate réversible) de l'automate universel équivalent. De plus, il existe un tel sous-automate sur lequel on peut calculer une expression rationnelle qui représente le langageavec une hauteur d'étoile minimale. D'autre part, nous donnons un algorithme pour décider la séquentialité d'une série (max,+) ou (min,+) réalisée par par un automate sur un alphabet à une lettre. La complexité de cet algorithme ne dépend que de la structure de l'automate et non des valeurs des coefficients. Nous présentons aussi un algorithme qui permet de procéder directement à la déterminisation d'un automate réalisant une série séquentielle et, si ce n'est pas le cas, à l'obtention d'un automate équivalent non ambigu. Ce dernier point rejoint le résultat de Stéphane Gaubert qui montre qu'on peut obtenir une expression (et donc un automate) non ambiguë pour n'importe quel série (max,+) rationnelle sur une lettre. Enfin, nous proposons un algorithme pour construire, à partir d'une expression rationnelle avec multiplicité, un automate qui représente la même série. Cet algorithme, qui est la généralisation des travaux d'Antimirov, permet d'obtenir explicitement un ensemble fini d'expressions qui représentent un ensemble générateur du semi-module auquel appartiennent les quotients de la série rationnelle.

Les automates d'ordres, plus connus sous le nom de Message sequence Charts (MSC), ont connu une énorme popularité depuis les années 1990. Ce succès est à la fois académique et industriel. Les raisons de ce succès sont multiples : le modèle est simple et s'apprend très vite. De plus il possède une puissance d'expression supérieure à celle des automates finis, et pose des problèmes difficiles. L'apparente simplicité des MSCs est en fait trompeuse, et de nombreuses manipulations algorithmiques se révèlent rapidement être des problèmes indécidables. Dans ce document, nous revenons sur 10 années de recherches sur les Message Sequence Charts, et plus généralement sur les langages de scénarios, et tirons quelques conclusions à partir des travaux effectués. Nous revenons sur les propriétés formelles des Message Sequence charts, leur décidabilité, et les sous-classes du langage permettant la décision de tel ou tel problème. L'approche classique pour traiter un problème sur les MSCs est de trouver la plus grande classe possible sur laquelle ce problème est décidable. Un autre challenge est d'augmenter la puissance d'expression des MSCs sans perdre en décidabilité. Nous proposons plusieurs extensions de ce type, permettant la crétion dynamique de processus, ou la définition de protocoles de type "fenêtre glissante". Comme tout modèle formel, les MSCs peuvent difficilement dépasser une taille critique au delà de laquelle un utilisateur ne peut plus vraiment comprendre le diagramme qu'il a sous les yeux. Pour pallier à cette limite, une solution est de travailler sur de plus petits modules comportementaux, puis de les assembler pour obtenir des ensembles de comportements plus grands. Nous étudions plusieurs mécanismes permettant de composer des MSCs, et sur la robustesses des sous-classes de scénarios connues à la composition. La conclusion ce cette partie est assez négative: les scénarios se composent difficilement, et lorsqu'une composition est faisable, peu de propriétés des modèles composés sont préservées. Nous apportons ensuite une contributions à la synthèse automatique de programmes distribués à partir de spécification données sous forme d'automates d'ordres. Cette question répond à un besoin pratique, et permet de situer un role possible des scénarios dans des processus de conception de logiciels distribués. Nous montrons que la synthèse automatique est possible sur un sous ensemble raisonnable des automates d'ordres. Dans une seconde partie de ce document, nous étudions des applications possibles pour les MSCs. Nous regardons entre autres des algorithmes de model-checking, permettant de découvrir des erreurs au moment de la spécification d'un système distribué par des MSCs. La seconde application considérée est le diagnostic, qui permet d'expliciter à l'aide d'un modèle les comportement d'un système réel instrumenté. Enfin, nous regardons l'utilisation des MSCs pour la recherche de failles de sécurité dans un système. Ces deux applications montrent des domaines réalistes d'utilisation des scénarios. Pour finir, nous tirons quelques conclusions sur les scénarios au regard du contenu du document et du travail de ces 10 dernières années. Nous proposons ensuite quelques perspectives de recherche.

Este trabalho é um estudo inicial sobre a integração de duas áreas da engenharia da computação, as tecnologias adaptativas e os algoritmos genéticos. Para tanto, foi realizada a aplicação de algoritmos genéticos na inferência de autômatos adaptativos. Várias tácnicas foram estudas e propostas para a implementação do algoritmo, visando µa obtenção de resultados cada vez mais satisfatórios. Ambas as tecnologias, algoritmos genéticos e tecnologia adaptativa, possuem caráter fortemente adaptativo, porém com características bastante diferentes na forma que são implementadas e executadas. As inferências, propostas neste trabalho, foram realizadas com sucesso, de maneira que as técnicas descritas podem ser empregadas em ferramentas de auxílio para projetistas desses tipos de dispositivos. Ferramentas que podem vir a ser úteis devido µa complexidade envolvida no desenvolvimento de um autômato adaptativo. Através desta aplicação dos algoritmos genéticos, observando como os autômatos evoluíram durante a execução dos ensaios realizados, acredita-se que foi obtido um entendimento melhor da estrutura e funcionamento dos autômatos adaptativos e de como essas duas tecnologias, tão importantes, podem ser combinadas. / This work is an initial study about the integration of two computing engineering areas, the adaptive technologies and the genetic algorithms. For that, it was per- formed the application of genetic algorithms for the adaptive automata inference. Several techniques were studied and proposed along the algorithm implementation, always seeking for more satisfying results. Both technologies, genetic algorithm and adaptive technology, hold very strong adaptive features, however, with very di®erent characteristics in the way they are implemented and executed. The inferences, proposed in this work, were performed with success, so that the techniques described may be employed in aid tools for designers of such de- vices. Tools that may be useful due to the complexity involved in the development of an adaptive automaton. Through this genetic algorithm application, observing how automata evolved during the algorithm execution, we believe that it was obtained a better under- standing about the adaptive automaton structure and how those two, so impor- tant, technologies can be integrated.