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.