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.

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.

Characteristics of effective clinical and theory instructors as perceived by LPN to RN versus generic students in an associate degree nursing program

The purpose of this study was to compare the characteristics of effective clinical and theory instructors as perceived by LPN/RN versus generic students in an associate degree nursing program.^ Data were collected from 508 students during the 1996-7 academic year from three NLN accredited associate degree nursing programs. The researcher developed instrument consisted of three parts: (a) Whitehead Characteristics of Effective Clinical Instructor Rating Scale, (b) Whitehead Characteristics of Effective Theory Instructor Rating Scale, and (c) Demographic Data Sheet. The items were listed under five major categories identified in the review of the literature: (a) interpersonal relationships, (b) personality traits, (c) teaching practices, (d) knowledge and experience, and (e) evaluation procedures. The instrument was administered to LPN/RN students in their first semester and to generic students in the third semester of an associate degree nursing program.^ Data was analyzed using a one factor mutivariate analysis of variance (MANOVA). Further t tests were carried out to explore for possible differences between type of student and by group. Crosstabulations of the demographic data were analyzed.^ There were no significant differences found between the LPN/RN versus generic students on their perceptions of either effective theory or effective clinical instructor characteristics. There were significant differences between groups on several of the individual items. There was no significant interaction between group and ethnicity or group and age on the five major categories for either of the two instruments. There was a significant main effect of ethnicity on several of the individual items.^ The differences between the means and standard deviations on both instruments were small, suggesting that all of the characteristics listed for effective theory and clinical instructors were important to both groups of students. Effective teaching behaviors, as indicated on the survey instruments, should be taught to students in graduate teacher education programs. These behaviors should also be discussed by faculty coordinators supervising adjunct faculty. Nursing educators in associate degree nursing programs should understand theories of adult learning and implement instructional strategies to enhance minority student success. ^