No description available.

No description available.

No description available.

No description available.

Thesis (Ph. D.)--University of Hawaii at Manoa, 1994. / Includes bibliographical references (leaves 350-354). / Microfiche. / xx, 354 leaves, bound ill. 29 cm

Thesis (Ph. D.)--University of Hawaii at Manoa, 1995. / Includes bibliographical references (leaves 220-227). / Microfiche. / xiii, 227 leaves, bound ill. (some col.) 29 cm

Expressed sequence tag database is a rich and fast growing source of data for gene expression analysis and drug discovery. Clustering of raw EST data is a necessary step for further analysis and one of the most challenging problems of modem computational biology.

The goal of Inductive Learning is to produce general rules from a set of seen examples, which can then be applied to other unseen examples. ID3 is an inductive learning algorithm that can be used for the classification task. The input to the algorithm is a set of tuples of description and class. The ID3 algorithm learns a decision tree from these input examples, which can then be used for classifying unseen examples given their descriptions. ID3 faces a problem called the replication problem. An algorithm called the Expert-Gate algorithm is presented in this thesis. The aim of the algorithm is to tackle the replication problem. We discuss the various issues involved with each step of the algorithm and present results corroborating our choices. The algorithm was tested on various artificially created problems as well as on a real life problem. The performance of the algorithm was compared with that of Fringe. The algorithm was found to give excellent results on the artificially created problems. The Expert-Gate algorithm gave satisfactory results on the NETtalk problem. Overall, we believe the algorithm is a good candidate for testing on other real life domains. / Graduation date: 1993

Knowledge compilation improves search-intensive problem-solvers that are easily specified but inefficient. One promising approach improves efficiency by constructing a database of problem-instance/best-action pairs that replace problem-solving search with efficient lookup. The database is constructed by reverse enumeration- expanding the complete search space backwards, from the terminal problem instances. This approach has been used successfully in counter-planning to construct perfect problem-solvers for sub domains of chess and checkers. However, the approach is limited to small problems because both the space needed to store the database and the time needed to generate the database grow exponentially with problem size. This thesis addresses these problems through two mechanisms. First, the space needed is reduced through an abstraction mechanism that is especially suited to counter-planning domains. The search space is abstracted by representing problem states as equivalence classes with respect to the goal achieved and the operators as equivalence classes with respect to how they influence the goals. Second, the time needed is reduced through a hueristic best-first control of the reverse enumeration. Since with larger problems it may be impractical to run the compiler to completion, the search is organized to optimize the tradeoff between the time spent compiling a domain and the coverage achieved over that domain. These two mechanisms are implemented in a system that has been applied to problems in chess and checkers. Empirical results demonstrate both the strengths and weaknesses of the approach. In most problems and 80/20 rule was demonstrated, where a small number of patterns were identified early that covered most of the domain, justifying the use of best-first search. In addition, the method was able to automatically generate a set of abstract rules that had previously required two person-months to hand engineer. / Graduation date: 1992

Very large graphs are difficult for a person to browse and edit on a computer screen. This thesis introduces a visual formalism, structured graphs, which supports the scalable browsing and editing of very large graphs. This approach is relevant to a given application when it incorporates a large graph which is composed of named nodes and links, and abstraction hierarchies which can be defined on these nodes and links. A typical browsing operation is the selection of an arbitrary group of nodes and the display of the network of nodes and links for these nodes. Typical editing operations is: adding a new link between two nodes, adding a new node in the hierarchy, and moving sub-graphs to a new position in the node hierarchy. These operations are scalable when the number of user steps involved remains constant regardless of how large the graph is. This thesis shows that with structured graphs, these operations typically take one user step. We demonstrate the utility of structured graph formalism in an application setting. Computer aided software engineering tools, and in particular, structured analysis tools, are the chosen application area for this thesis, as they are graph based, and existing tools, though adequate for medium sized systems, lack scalability. In this thesis examples of an improved design for a structured analysis tool, based on structured graphs, is given. These improvements include scalable browsing and editing operations to support an individual software analyst, and component composition operations to support the construction of large models by a group of software analysts. Finally, we include proofs of key properties and descriptions of two text based implementations.