Molecular phylogenetics of the palm tribe Geonomeae, and differentiation of Geonoma macrostachys western Amazonian varieties

Phylogenetic analyses were performed on six genera and 46 species of the Neotropical palm tribe Geonomeae. The analyses were based on two low copy nuclear DNA sequences from the genes encoding phosphoribulokinase and RNA polymerase II. The basal node of the tribe was polytomous. Pholidostachys formed a monophyletic group. The currently accepted genera Calyptronoma and Calyptrogyne formed a well-supported clade with Calyptronoma resolved as paraphyletic to Calyptrogyne. Geonoma formed a strongly supported monophyletic group consisting of two main clades. ^ An evaluation of the genetic distinctness between Geonoma macrostachys varieties at a local and regional scale using inter-simple sequence repeat (ISSR) markers was performed. Clustering, ordination, and AMOVA suggested a lack of genetic distinctness between varieties at the regional level. A hierarchical AMOVA revealed that the genetic diversity mainly lies among the four localities sampled. A significant genetic differentiation between sympatric varieties occurred in one locality only. The current taxonomy of G. macrostachys, which recognizes only one species, was therefore supported. ^ The preferred habitat of sympatric G. macrostachys varieties with respect to edaphic, topographic, and light factors in three Peruvian lowland forests was studied. The two varieties were mostly encountered in different physiographically defined habitats, with variety acaulis occurring more often in floodplain forest and variety macrostachys in the tierra firme. Comparison of means tests revealed that nine to eleven of the 16 environmental variables were significantly different between varieties. Edaphic factors, mainly soil texture and K content, were better contributors than light conditions to distinguish the habitats occupied by the two varieties in all three study sites. It is concluded that habitat differentiation plays a role in the coexistence of these closely related species taxa. ^

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.