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.

Discussion Paper: Triangulation of Methodology to Solve the Practitioner - Academic Debate Concerning the Value of Research

In support of research in the debate concerning its relevance to hospitality academics and practitioners, the author presents a discussion of how the philosophy of science impacts approaches to research, including a brief summary of empiricism, and the importance of the triangulation of research orientations. Criticism of research is the hospitality literature often focuses on the lack of an apparent philosophy of science perspective and how this perspective impacts the way in which scholars conduct and interpret research. The Validity Network Schema (VNS) presents a triangulation model for evaluating research progress in a discipline by providing a mechanism for integrating academic and practitioner research studies.

Assessing Organizational Image: Triangulation Across Different Applicant Perceptions, Website, and Facebook Features

This study examined the role of corporate websites and company Facebook profiles in shaping perceptions of organizational image in the recruitment context. A primary purpose of this research was to determine whether or not perceptions of organizational image vary across different web-based recruitment methods, specifically examining corporate websites and social networking (SNW) sites, such as company Facebook profiles. A secondary goal was to determine how these perceptions of image are shaped by the objective components of websites and Facebook profiles. Finally, this study sought to determine the most influential components of websites and Facebook profiles, in terms of impacting image, to better understand how organizations can maximize their web-based recruitment efforts. A total of 102 companies selected from Fortune Magazine’s 2011 top 500 were chosen for the study. Perceptions of organizational personality as well as objective assessments of personality were gathered for each organization in a two phase approach. Results indicate that exposure to corporate websites and company Facebook profiles do influence perceptions of image in different ways. Furthermore, individual components of the websites were identified as key drivers for influencing specific image dimensions, particularly for company Facebook pages. Findings are beneficial for advising practitioners on how to best manage their web-based recruitment sources in order to maximize efficiency. The present study serves to further our understanding of the process through which perceptions of organizational image are influenced by new recruitment sources.

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.