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.

The European Parliament, membership expansions, and organizational change

The European Union (EU) is an extraordinary achievement. From a regional economic organization, it grew into a polity within fifty years. The original EU of six members expanded incrementally to 27 over forty years, and it now comprises a population of almost 500 million people. While the five expansions of the European Economic Community/European Community/European Union (EU) have received considerable scholarly attention, surprisingly little attention has been given to their impacts on "Europe's" only legislative body, currently known as the European Parliament (EP). More specifically, little is known about how waves of new members (from widely diverse parties and national backgrounds) affected—and were affected by—the EP's organizational structure and its internal processes. The purpose of this study therefore is to help fill this gap by describing and explaining how the various EEC/EC/EU expansions or "membership shocks" (1973, 1981, 1986, 1995, and 2004) affected the EP's organizational structure and its internal Rules of Procedure (RoP). The central research question of this dissertation is the following: What were the major structural and procedural effects of the five membership expansions of what eventually became the European Union on the European Parliament? This dissertation answers this question by using concepts and measures drawn from organizational theory. While other studies have applied concepts and hypotheses from organizational theory to legislatures, such an approach has never been used to analyze the EP, which is conceptualized here as a "membership organization." This study, through an analysis of the EP, demonstrates that organization theory can help us fully understand the effects of membership expansions on any membership organization. That is, understanding how this particular organization responded to change can inform not only how others in this class (legislatures) do so, but how this process unfolds in a variety of times and places. The principal findings of this study are as follows: (1) EP staff growth revealed an interesting pattern: Staff did not increase concurrently with EP membership. That is, it turned out that the rate of membership growth exceeded the rate of staff increase, suggesting professionalization of EP staff and their relative empowerment vis-à-vis MEPs; (2) The number of rules and the precision within them increased; (3) the largest number of EP rule changes focused on increasing EP efficiency; and (4) The authority was centralized in the hands of EP leadership, that is, the EP President, the Conference of Presidents and also two major political groups.

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.