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.

Islam and Christianity: Comparing the Theory of Supersession Concerning Abraham

Supersession is the theory of one idea supplanting the other. In both Christianity and Islam, this idea is commonplace. In Christianity, the message of Jesus creates a New Covenant for both Jews and Gentiles, while in Islam, the revelation of Muhammad restores the original religion that God intended from the beginning. Christianity and Islam both supersede Judaism in very similar ways. In regards to the use of Abraham in particular, each religion inherits him by appealing to Jewish scripture or their oral tradition, using him to prove their truth claims, and claiming that their religion is originally the religion of Abraham.

Extending the Theory of Planned Behavior in the Exercise Domain: A Study of Community College Students in an Urban Multicultural Setting

The purpose of this study was to assess the intention to exercise among ethnically and racially diverse community college students using the Theory of Planned Behavior (TPB). In addition to identifying the variables associated with motivation or intention of college students to engage in physical activity, this study tested the model of the Theory of Planned Behavior, asking: Does the TPB model explain intention to exercise among a racially/ethnically diverse group of college students? The relevant variables were the TPB constructs (behavioral beliefs, normative beliefs, and control beliefs), which combined to form a measure of intention to exercise. Structural Equation Modeling was used to test the predictive power of the TPB constructs for predicting intention to exercise. Following procedures described by Ajzen (2002), the researcher developed a questionnaire encompassing the external variables of student demographics (age, gender, work status, student status, socio-economic status, access to exercise facilities, and past behavior), major constructs of the TPB, and two questions from the Godin Leisure Time Questionnaire (GLTQ; Godin & Shephard, 1985). Participants were students (N = 255) who enrolled in an on-campus wellness course at an urban community college. The demographic profile of the sample revealed a racially/ethnically diverse study population. The original model that was used to reflect the TPB as developed by Ajzen was not supported by the data analyzed using SEM; however, a revised model that the researcher thought was theoretically a more accurate reflection of the causal relations between the TPB constructs was supported. The GLTQ questions were problematic for some students; those data could not be used in the modeling efforts. The GLTQ measure, however, revealed a significant correlation with intention to exercise (r = .27, p = .001). Post-hoc comparisons revealed significant differences in normative beliefs and attitude toward exercising behavior between Black students and Hispanic students. Compared to Black students, Hispanic students were more likely to (a) perceive “friends” as approving of them being physically active and (b) rate being physically active for 30 minutes per day as “beneficial”. No statistically significant difference was found among groups on overall intention to exercise.