Algebraic theory of minimal nondeterministic finite automata with applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA’s behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

Phonics instruction using pseudowords for success in phonetic decoding

This study examined a Pseudoword Phonics Curriculum to determine if this form of instruction would increase students’ decoding skills compared to typical real-word phonics instruction. In typical phonics instruction, children learn to decode familiar words which allow them to draw on their prior knowledge of how to pronounce the word and may detract from learning decoding skills. By using pseudowords during phonics instruction, students may learn more decoding skills because they are unfamiliar with the “words” and therefore cannot draw on memory for how to pronounce the word. It was hypothesized that students who learn phonics with pseudowords will learn more decoding skills and perform higher on a real-word assessment compared to students who learn phonics with real words. ^ Students from two kindergarten classes participated in this study. An author-created word decoding assessment was used to determine the students’ ability to decode words. The study was broken into three phases, each lasting one month. During Phase 1, both groups received phonics instruction using real words, which allowed for the exploration of baseline student growth trajectories and potential teacher effects. During Phase 2, the experimental group received pseudoword phonics instruction while the control group continued real-word phonics instruction. During Phase 3, both groups were taught with real-word phonics instruction. Students were assessed on their decoding skills before and after each phase. ^ Results from multiple regression and multi-level model analyses revealed a greater increase in decoding skills during the second and third phases of the study for students who received the pseudoword phonics instruction compared to students who received the real-word phonics instruction. This suggests that pseudoword phonics instruction improves decoding skills quicker than real-word phonics instruction. This also suggests that teaching decoding with pseudowords for one month can continue to improve decoding skills when children return to real-word phonics instruction. Teacher feedback suggests that confidence with reading increased for students who learned with pseudowords because they were less intimidated by the approach and viewed pseudoword phonics as a game that involved reading “silly” words. Implications of these results, limitations of this study, and areas for future research are discussed. ^

Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

Phonics Instruction using Pseudowords for Success in Phonetic Decoding

This study examined a Pseudoword Phonics Curriculum to determine if this form of instruction would increase students’ decoding skills compared to typical real-word phonics instruction. In typical phonics instruction, children learn to decode familiar words which allow them to draw on their prior knowledge of how to pronounce the word and may detract from learning decoding skills. By using pseudowords during phonics instruction, students may learn more decoding skills because they are unfamiliar with the “words” and therefore cannot draw on memory for how to pronounce the word. It was hypothesized that students who learn phonics with pseudowords will learn more decoding skills and perform higher on a real-word assessment compared to students who learn phonics with real words. Students from two kindergarten classes participated in this study. An author-created word decoding assessment was used to determine the students’ ability to decode words. The study was broken into three phases, each lasting one month. During Phase 1, both groups received phonics instruction using real words, which allowed for the exploration of baseline student growth trajectories and potential teacher effects. During Phase 2, the experimental group received pseudoword phonics instruction while the control group continued real-word phonics instruction. During Phase 3, both groups were taught with real-word phonics instruction. Students were assessed on their decoding skills before and after each phase. Results from multiple regression and multi-level model analyses revealed a greater increase in decoding skills during the second and third phases of the study for students who received the pseudoword phonics instruction compared to students who received the real-word phonics instruction. This suggests that pseudoword phonics instruction improves decoding skills quicker than real-word phonics instruction. This also suggests that teaching decoding with pseudowords for one month can continue to improve decoding skills when children return to real-word phonics instruction. Teacher feedback suggests that confidence with reading increased for students who learned with pseudowords because they were less intimidated by the approach and viewed pseudoword phonics as a game that involved reading “silly” words. Implications of these results, limitations of this study, and areas for future research are discussed.

Locally recurrent functions, density topologies and algebraic genericity

We study the algebraic and topological genericity of certain subsets of locally recurrent functions, obtaining (among other results) algebrability and spaceability within these classes.

Locally recurrent functions, density topologies and algebraic genericity

We study the algebraic and topological genericity of certain subsets of locally recurrent functions, obtaining (among other results) algebrability and spaceability within these classes.

Decoding Spontaneous Emotional States in the Human Brain.

Pattern classification of human brain activity provides unique insight into the neural underpinnings of diverse mental states. These multivariate tools have recently been used within the field of affective neuroscience to classify distributed patterns of brain activation evoked during emotion induction procedures. Here we assess whether neural models developed to discriminate among distinct emotion categories exhibit predictive validity in the absence of exteroceptive emotional stimulation. In two experiments, we show that spontaneous fluctuations in human resting-state brain activity can be decoded into categories of experience delineating unique emotional states that exhibit spatiotemporal coherence, covary with individual differences in mood and personality traits, and predict on-line, self-reported feelings. These findings validate objective, brain-based models of emotion and show how emotional states dynamically emerge from the activity of separable neural systems.

Recoding: reprogrammed genetic decoding with an emphasis on antizyme regulatory frameshifting

Recoding embraces mechanisms that augment the rules of standard genetic decoding. The deviations from standard decoding are often purposeful and their realisation provides diverse and flexible regulatory mechanisms. Recoding events such as programed ribosomal frameshifting are especially plentiful in viruses. In most organisms only a few cellular genes are known to employ programed ribosomal frameshifting in their expression. By far the most prominent and therefore well-studied case of cellular +1 frameshifting is in expression of antizyme mRNAs. The protein antizyme is a key regulator of polyamine levels in most eukaryotes with some exceptions such as plants. A +1 frameshifting event is required for the full length protein to be synthesized and this requirement is a conserved feature of antizyme mRNAs from yeast to mammals. The efficiency of the frameshifting event is dependent on the free polyamine levels in the cell. cis-acting elements in antizyme mRNAs such as specific RNA structures are required to stimulate the frameshifting efficiency. Here I describe a novel stimulator of antizyme +1 frameshifting in the Agaricomycotina class of Basidiomycete fungi. It is a nascent peptide that acts from within the ribosome exit tunnel to stimulate frameshifting efficiency in response to polyamines. The interactions of the nascent peptide with components of the peptidyl transferase centre and the protein exit tunnel emerge in our understanding as powerful means which the cell employs for monitoring and tuning the translational process. These interactions can modulate the rate of translation, protein cotranslational folding and localization. Some nascent peptides act in concert with small molecules such as polyamines or antibiotics to stall the ribosome. To these known nascent peptide effects we have added that of a stimulatory effect on the +1 frameshifting in antizyme mRNAs. It is becoming evident that nascent peptide involvement in regulation of translation is a much more general phenomenon than previously anticipated.

A monoidal algebraic model for rational SO(2)-spectra

The category of rational SO(2)--equivariant spectra admits an algebraic model. That is, there is an abelian category A(SO(2)) whose derived category is equivalent to the homotopy category of rational$SO(2)--equivariant spectra. An important question is: does this algebraic model capture the smash product of spectra? The category A(SO(2)) is known as Greenlees' standard model, it is an abelian category that has no projective objects and is constructed from modules over a non--Noetherian ring. As a consequence, the standard techniques for constructing a monoidal model structure cannot be applied. In this paper a monoidal model structure on A(SO(2)) is constructed and the derived tensor product on the homotopy category is shown to be compatible with the smash product of spectra. The method used is related to techniques developed by the author in earlier joint work with Roitzheim. That work constructed a monoidal model structure on Franke's exotic model for the K_(p)--local stable homotopy category. A monoidal Quillen equivalence to a simpler monoidal model category that has explicit generating sets is also given. Having monoidal model structures on the two categories removes a serious obstruction to constructing a series of monoidal Quillen equivalences between the algebraic model and rational SO(2)--equivariant spectra.

ImageLearn - Decoding Britain's Landscape

Abstract Ordnance Survey, our national mapping organisation, collects vast amounts of high-resolution aerial imagery covering the entirety of the country. Currently, photogrammetrists and surveyors use this to manually capture real-world objects and characteristics for a relatively small number of features. Arguably, the vast archive of imagery that we have obtained portraying the whole of Great Britain is highly underutilised and could be ‘mined’ for much more information. Over the last year the ImageLearn project has investigated the potential of "representation learning" to automatically extract relevant features from aerial imagery. Representation learning is a form of data-mining in which the feature-extractors are learned using machine-learning techniques, rather than being manually defined. At the beginning of the project we conjectured that representations learned could help with processes such as object detection and identification, change detection and social landscape regionalisation of Britain. This seminar will give an overview of the project and highlight some of our research results.

Problems in Algebraic Vision

Thesis (Ph.D.)--University of Washington, 2016-08