Interactions between DNA molecules can be used to perform computation. These DNA computing systems often use DNA molecules as freely diusing reactants in a well-mixed solution. We demonstrate how DNA walkers tethered to an origami-templated track can perform computation. A DNA walker can block a track that intersects with its own, preventing another walker from stepping down this blocked track. These blockages are primitive operations that can be used to perform computation. This thesis demonstrates how blocking interactions between DNA walkers can evaluate formulae posed in propositional logic. When anchorages in the track are viewed as networked machines and the DNA walker is viewed as a coordinated message passed between them, DNA walker circuits can be modelled as a distributed system. Techniques from formal veri- cation can be used to check this system for errors, determining the probability with which the system will end up in a certain state. This forms the basis of a compiler that can automatically design a DNA walker circuit that evaluates a given propositional formula within a specied error tolerance. To show how DNA walker circuits can be simplied, we create a propositional logic system called blocking logic that is proven to be both sound and complete. DNA walker circuits can be implemented and measured experimentally by using fluorescence spectrophotometry to track the position of a walker on the track. To demonstrate proof of principle, circuits were built that implement NOT and NOR operators. To make these circuits operate with minimal error, dierent sources of possible error were investigated and quantied. Cumulatively, the novel contributions that this thesis makes to the eld are: • the experimental design and implementation of a DNA computing system that uses DNA walkers, • probabilistic model checking software that automatically designs these DNA walker circuits, • a propositional logic system that can simplify a DNA walker circuit to an equivalent circuit that uses fewer tracks.

No description available.

No description available.

As more students interact with online learning platforms and eTextbooks, they generate massive amounts of data. For example, the OpenDSA eTextbook system collects clickstream data as users interact with prose, visualizations, and interactive auto-graded exercises. Ideally, instructors and system developers can harness this information to create better instructional experiences. But in its raw event-level form, it is difficult for developers or instructors to understand student behaviors, or to make testable hypotheses about relationships between behavior and performance. In this study, we describe our efforts to break raw event-level data first into sessions (a continuous series of work by a student) and then to meaningfully abstract the events into higher-level descriptions of that session. The goal of this abstraction is to help instructors and researchers gain insights into the students' learning behaviors. For example, we can distinguish when students read material and then attempt the associated exercise, versus going straight to the exercise and then hunting for the answers in the associated material. We first bundle events into related activities, such as the events associated with stepping through a given visualization, or with working a given exercise. Each such group of events defines a state. A state is a basic unit that characterizes the interaction log data, and there are multiple state types including reading prose, interacting with visual contents, and solving exercises. We harnessed the abstracted data to analyze studying behavior and compared it with course performance based on GPA. We analyzed data from the Fall 2020 and Spring 2021 sections of a senior-level Formal Languages course, and also from the Fall 2020 and Spring 2021 sections of a data structures course. / Master of Science / OpenDSA is an online learning platform used in multiple academic institutions including Virginia Tech's Computer Science courses. They use OpenDSA as the main instructional method and students in these courses generate massive amounts of clickstream data while interacting with the OpenDSA content. The system collects various events logs such as when students opened/closed a certain page, how long they stayed on the page, and how many times they clicked an interface element for visualizations and exercises. However, in its raw event-level form, it is difficult for instructors or developers to understand student behaviors, or to make testable hypotheses about relationships between behavior and performance. We describe our efforts to break raw event-level clickstreams into a session (continuous series of work by a student) and then to abstract the events into meaningful higher-level descriptions of students' behavior. We grouped raw events into related activities, such as the events associated with stepping through a given visualization, or working with a given exercise. We defined such a group of activities as a state, which is a basic unit that can characterize the interaction log data such as reading, slideshows, and exercises state. We harnessed the abstracted data to analyze students' studying behavior and compared it with their course performance based on their GPA. We analyzed data from two offerings of two CS courses at Virginia Tech to gain insights into students' learning behaviors.

Orientador: Marcelo Esteban Coniglio / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-11T21:55:18Z (GMT). No. of bitstreams: 1 Reis_TeofilodeSouza_M.pdf: 733611 bytes, checksum: 0e64d330d9e71079eddd94de91f141c2 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho apresentamos um novo formalismo de decomposição de Lógicas, as Coberturas por Traduções Possíveis, ou simplesmente CTPs. As CTPs constituem uma versão formal das Semânticas de Traduções Possíveis, introduzidas por W. Carnielli em 1990. Mostramos como a adoção de um conceito mais geral de morfismo de assinaturas proposicionais (usando multifunções no lugar de funções) nos permite definir uma categoria Sig?, na qual os conectivos, ao serem traduzidos de uma assinatura para outra, gozam de grande flexibilidade. A partir de Sig?, contruímos a categoria Log? de lógicas tarskianas e morfismos (os quais são funções obtidas a partir de um morfismo de assinaturas, isto é, de uma multifunção). Estudamos algumas características de Sig? e Log?, afim de verificar que estas categorias podem de fato acomodar as construções que pretendemos apresentar. Mostramos como definir em Log? o conjunto de traduções possíveis de uma fórmula, e a partir disto definimos a noção de CTP para uma lógica L. Por fim, exibimos um exemplo concreto de utilização desta nova ferramenta, e discutimos brevemente as possíveis abordagens para uma continuação deste trabalho. / Abstract: We present a general study of a new formalism of decomposition of logics, the Possible- Translations Coverings (in short PTC 's) which constitute a formal version of Possible-Translations Semantics, introduced by W. Carnielli in 1990. We show how the adoption of a more general notion of propositional signatures morphism allows us to define a category Sig?, in which the connectives, when translated from a signature to another one, enjoy of great flexibility. Essentially, Sig? -morphisms will be multifunctions instead of functions. From Sig? we construct the category Log? of tarskian logics and morphisms between them (these .are functions obtained from signature morphisms, that is, from multifunctions) . We show how to define in Log? the set of possible translations of a given formula, and we define the notion of a PTC for a logic L. We analyze some properties of PTC 's and give concrete examples of the above mentioned constructions. We conclude with a discussion of the approaches to be used in a possible continuation of these investigations. / Mestrado / Mestre em Filosofia

Call number: LD2668 .T4 1985 J63 / Master of Science

Cette thèse adresse les problèmes d'universalité et de complétude computationelle pour plusieurs modèles de calcul inspirés par la biologie. Il s'agit principalement des systèmes d'insertion/effacement, réseaux de processeurs évolutionnaires, ainsi que des systèmes de réécriture de multi-ensembles. Les résultats décrits se classent dans deux catégories majeures : l'étude de la puissance de calcul des opérations d'insertion et d'effacement avec ou sans mécanismes de contrôle, et la construction des systèmes de réécriture de multi-ensembles universels de petite taille. Les opérations d'insertion et d'effacement consistent à rajouter ou supprimer une sous-chaîne dans une chaîne de caractères dans un contexte donné. La motivation pour l'étude de ces opérations vient de la biologie, ainsi que de la linguistique et de la théorie des langages formels. Dans la première partie de ce manuscrit nous examinons des systèmes d'insertion/effacement correspondant à l'édition de l'ARN, un processus qui insère ou supprime des fragments de ces molécules. Une particularité importante de l'édition de l'ARN est que le endroit auquel se font les modifications est déterminé par des séquences de nucléotides se trouvant toujours du même côté du site de modification. En termes d'insertion et d'effacement, ce phénomène se modéliserait par des règles possédant le contexte uniquement d'un seul côté. Nous montrons qu'avec un contexte gauche de deux caractères il est possible d'engendrer tous les langages rationnels. D'autre part, nous prouvons que des contextes plus longs n'augmentent pas la puissance de calcul du modèle. Nous examinons aussi les systèmes d’insertion/effacement utilisant des mécanismes de contrôle d’application des règles et nous montrons l'augmentation de la puissance d'expression. Les opérations d'insertion et d'effacement apparaissent naturellement dans le domaine de la sécurité informatique. Comme exemple on peut donner le modèle des grammaires gauchistes (leftist grammar), qui ont été introduites pour l'étude des systèmes critiques. Dans cette thèse nous proposons un nouvel instrument graphique d'analyse du comportement dynamique de ces grammaires. La deuxième partie du manuscrit s'intéresse au problème d'universalité qui consiste à trouver un élément concret capable de simuler le travail de n'importe quel autre dispositif de calcul. Nous commençons par le modèle de réseaux de processeurs évolutionnaires, qui abstrait le traitement de l'information génétique. Nous construisons des réseaux universels ayant un petit nombre de règles. Nous nous concentrons ensuite sur les systèmes de réécriture des multi-ensembles, un modèle qui peut être vu comme une abstraction des réactions biochimiques. Pour des raisons historiques, nous formulons nos résultats en termes de réseaux de Petri. Nous construisons des réseaux de Petri universels et décrivons des techniques de réduction du nombre de places, de transitions et d'arcs inhibiteurs, ainsi que du degré maximal des transitions. Une bonne partie de ces techniques repose sur une généralisation des machines à registres introduite dans cette thèse et qui permet d'effectuer plusieurs tests et opérations en un seul changement d'état / The present thesis considers the problems of computational completeness and universality for several biologically-inspired models of computation: insertion-deletion systems, networks of evolutionary processors, and multiset rewriting systems. The presented results fall into two major categories: study of expressive power of the operations of insertion and deletion with and without control, and construction of universal multiset rewriting systems of low descriptional complexity. Insertion and deletion operations consist in adding or removing a subword from a given string if this subword is surrounded by some given contexts. The motivation for studying these operations comes from biology, as well as from linguistics and the theory of formal languages. In the first part of the present work we focus on insertion-deletion systems closely related to RNA editing, which essentially consists in inserting or deleting fragments of RNA molecules. An important feature of RNA editing is the fact that the locus the operations are carried at is determined by certain sequences of nucleotides, which are always situated to the same side of the editing site. In terms of formal insertion and deletion, this phenomenon is modelled by rules which can only check their context on one side and not on the other. We show that allowing one-symbol insertion and deletion rules to check a two-symbol left context enables them to generate all regular languages. Moreover, we prove that allowing longer insertion and deletion contexts does not increase the computational power. We further consider insertion-deletion systems with additional control over rule applications and show that the computational completeness can be achieved by systems with very small rules. The motivation for studying insertion-deletion systems also comes from the domain of computer security, for the purposes of which a special kind of insertion-deletion systems called leftist grammars was introduced. In this work we propose a novel graphical instrument for visual analysis of the dynamics of such systems. The second part of the present thesis is concerned with the universality problem, which consists in finding a fixed element able to simulate the work any other computing device. We start by considering networks of evolutionary processors (NEPs), a computational model inspired by the way genetic information is processed in the living cell, and construct universal NEPs with very few rules. We then focus on multiset rewriting systems, which model the chemical processes running in the biological cell. For historical reasons, we formulate our results in terms of Petri nets. We construct a series of universal Petri nets and give several techniques for reducing the numbers of places, transitions, inhibitor arcs, and the maximal transition degree. Some of these techniques rely on a generalisation of conventional register machines, proposed in this thesis, which allows multiple register checks and operations to be performed in a single state transition

Cette thèse traite des ensembles rationnels de mots indexés par des ordres linéaires et en particulier du problème de la fermeture par complémentation. Dans un papier fondateur de 1956, Kleene initie la théorie des langages en montrant que les automates sur les mots finis et les expressions rationnelles ont le même pouvoir d'expression. Depuis, ce résultat a été étendu à de nombreuses structures telles que les mots infinis (Büchi, Muller), bi-infinis (Beauquier, Nivat, Perrin), les mots indexés par des ordinaux (Büchi, Bedon), les traces, les arbres... Plus récemment, Bruyère et Carton ont introduit des automates acceptant des mots indexés par des ordres linéaires et des expressions rationnelles correspondantes. Ces structures linéaires comprennent les mots infinis, les mots indexés par des ordinaux et leurs miroirs. Le théorème de Kleene a été généralisé aux mots indexés par les ordres linéaires dénombrables et dispersés, c'est-à-dire les ordres ne contenant pas de sous-ordre isomorphe à Q. Pour la plupart des structures, la classe des ensembles rationnels forme une algèbre de Boole. Cette propriété est nécessaire pour traduire une logique en automates. La fermeture par complémentation restait un problème ouvert. Dans cette thèse, on résout ce problème de façon positive: on montre que le complément d'un ensemble rationnel de mots indexés par des ordres linéaires dispersés est rationnel. La méthode classique pour obtenir un automate acceptant le complémentaire d'un ensemble rationnel se fait par déterminisation. Nous montrons que cette méthode ne peut-être appliquée dans notre cas: tout automate n'est pas nécessairement équivalent à un automate déterministe. Nous avons utilisé d'autres approches. Dans un premier temps, nous généralisons la preuve de Büchi, basée sur une congruence de mots, et obtenons ainsi la fermeture par complémentation dans le cas des ordres linéaires de rang fini. Pour obtenir le résultat dans le cas général, nous utilisons l'approche algébrique. Nous développons une structure algébrique qui étend la reconnaissance classique par semigroupes finis : les semigroupes sont remplacés par les diamant-semigroupes qui possèdent un produit généralisé. Nous prouvons qu'un ensemble est rationnel si et seulement s'il est reconnu par un diamant-semigroupe fini. Nous montrons aussi qu'un diamant-semigroupe canonique, appelé diamant-semigroupe syntaxique, peut être associé à chaque ensemble rationnel. Notre preuve de la complémentation est effective. Le théorème de Schützenberger établit qu'un ensemble de mots finis est sans étoile si et seulement si son semigroupe syntaxique est fini et apériodique. Pour finir, nous étendons partiellement ce résultat au cas des ordres de rang fini.

No description available.

Uma sequência de imagens de satélite climático é processada aplicando-se um conjunto de operações de filtros, no intuito de extrair padrões de comportamento das nuvens. Caracteres são criados a partir deste tratamento e suas transições são investigadas, explorando a possibilidade de justificar suas ocorrências através de linguagens formais e linguagens bidimensionais, definindo suas gramáticas. Com esta contagem de transições, uma análise de sua forma fractal é iniciada e um paralelo com outras contagens estabelecida, como uma forma de estruturar um modelo computacionalmente menos complexo de prever o tempo, ou o comportamento de qualquer entidade dinâmica que possa ser discretizada. Com estas investigações e experiências, foi possível diminuir a quantidade de símbolos utilizados para justificar as formas das nuvens, bem como criar classes de equivalências para representar conjuntos de símbolos que compartilham as mesmas propriedades, diminuindo ainda mais a complexidade da gramática que se espera encontrar. / A sequence of weather satellite images are processed by applying a set of filtering operations in order to extract the behavior patterns of clouds. Characters are created from this treatment and their transitions are investigated by exploring the possibility of justifying their occurrence across formal languages and two-dimensional languages, defining their grammar. With these count transitions an analysis of their fractals starts and counts a parallel with others established as a way to structure a model less computationally complex to predict the weather, or the behavior of any dynamic entity that could be discretized. With these investigations and experiments, it was possible to reduce the number of symbols used to explain the shapes of clouds and create equivalent classes to represent the symbol sets that share the same properties, further reducing the complexity of the grammar expected to be found.