Information, both print and online is growing at an exponential rate. The ability to locate individual items of information has not kept pace. Once this information has been brought to bear on a problem, the resulting knowledge is lost. It is difficult to organize and store the results of an information search. We propose a tool to assist in the resolution of these problems. DocKMan's knowledge base builder. Through the use of a hierarchical concept organization and a frame-based inheritance scheme, we believe we have found a means of structuring information which allows easier browsing and retrieval of knowledge. The combination this 'structuring tool' with a text analysis tool facilitates the construction of organized repositories of knowledge or 'knowledge bases'. Text can now be analyzed for specific pieces of information which are then inserted into the appropriate area of the hierarchy. Such a set of tools will prove especially useful to knowledge workers in technically oriented fields.

Data Mining is extracting knowledge from data. Knowledge may be presented using rules which express relationships between sets of items involved in the rule. The nature and strength of the relationship is determined by an evaluation measure used to evaluate the rules. A relationship may correspond to an association, an implication, a correlation, a causality, a dependency, etc. This thesis considers the problem of finding the strongest N rules from transaction data. Existing algorithms (e.g. Apriori) employ search techniques based on Best-First Search methods which impose high demands on memory. Searching Depth-First solves this memory problem but can demand long execution time. This drawback can be avoided by using iterative deepening search where the Depth-First Search is run with a progressively relaxed search bound on each successive iteration. Relaxing the search bound can be based on various characteristics of the search space, such as a change in the tree depth (MSDD algorithm), or a change in the quality of states being explored. The key issue is the strategy by which the search bound is relaxed for subsequent iterations. We propose an iterative deepening search algorithm IDGmax using a search bound strategy based on the quality of states explored. We explore different methods for relaxing the search bound to improve the performance. We present experimental results to evaluate the performance of these search bound relaxation strategies and compare them to the MSDD algorithm. We also show that the choice of the search bound relaxation method can significantly influence the performance of the rule mining algorithm in both memory and time.

This thesis presents a mechanism based on eXtensible Markup Language (XML) to extract data from HTML-based Web pages and populate relational databases. This task is performed by a system called the XML-based Web Agent (XWA). The data extraction is done in three phases. First, the Web pages are converted to well-formed XML documents to facilitate their processing. Second, the data is extracted from the well-formed XML documents and formatted into valid XML documents. Finally, the valid XML documents are mapped into tables to be stored in a relational database. To extract specific data from the Web, the XWA requires information about the Web pages from which to extract the data, the location of the data within the Web pages, and how the extracted data should be formatted. This information is stored in Web Site Ontologies which are built using a language called the Web Ontology Description Language (WONDEL). WONDEL is based on XML and XML Pointer Language. It has been defined as a part of this work to allow users to specify the data they want, and let the XWA work offline to extract it and store it in a database. This has the advantage of saving users the time waiting for the Web pages to download, and taking benefit from the powerful query mechanism offered by database management systems.

The expanding availability of on-line information sources, such as on-line documents, corpora, and the World Wide Web, introduces some challenges. Most notably, users must search through this material to find high-quality, relevant information. This is the domain of information retrieval. Alternatively, knowledge bases present information in a very compact and structured representation. Unfortunately, their creation is labor intensive. In order to bridge the gap between the amount of structure in the information processed by information retrieval and knowledge engineering techniques, the author presents TAKODO, a tool and a framework designed for both (i) facilitating the extraction of knowledge from unstructured text, possibly to aid in the process of creating a knowledge base, and (ii) retrieving information from natural language texts and the knowledge base, using each to their mutual advantage. TAKODO integrates several existing applications, among them a question answering system, called Text Analyzer, and a frame-based knowledge management tool, called the Knowledge Organizer, with the additional support of corpus linguistic techniques.

This thesis addresses the problem of show-through in old manuscripts and documents. After removing the show-through these documents can be stored in the digital libraries and will be accessible by everybody via Internet. The solution to this problem utilizes the image restoration technique. To apply this, the documents are scanned from each side and stored in a digital form. The two sides of document are called recto and verso images. To approach an apposite solution a basic model of the degradation is defined for these two images and then this model is used to eliminate the show-through. The technique for the enhancement is divided into two parts---first, achieving the most precise registration technique and secondly, to compute a method of restoration using the model of degradation. Four different techniques for registration are compared to select the most suitable method for this problem. This comparison brings forth the affine transformation approach to register the image. An approach for the restoration of the registered images is defined to eliminate the show-through from the document and save it in a digital library.

A medical database is a valuable resource for medical research. By analyzing the patient records, the physicians can know better about the patient outcomes and resources utilization. In NICU where the medical resources are very expensive, it is particularly important for the physicians to know the relationship between the patient measurements and the outcomes (e.g. death, ventilation, length of stay, and other complications including lung disease and brain damage). Many techniques have been used in predicting or estimating patient outcomes in the literature. A backpropagation neural network (NN) was selected. Because neural networks cannot handle missing information, whereas incomplete patient records is a very common occurrence in the Neonatal Intensive Care Unit (NICU) database, two sets of experiments were conducted. In the first set of experiments, all the cases with missing information in a NICU database of about seven thousand patients were excluded. Only complete records were kept. In the second set of experiments, we tended to make full use of the records with missing information. The missing values were replaced with their NORMAL values. (Abstract shortened by UMI.)

The aim of this work is to show the usefulness of abstraction in heuristic search. We use the abstract spaces created by applying abstraction techniques to the original problem. These abstract spaces are then used to generate all the heuristic information necessary in order to find an optimal or near optimal solution to the original problem. One of our objectives is to preserve optimal paths while speeding up search. We have developed new approaches to speed-up A$\sp{*}$ in an abstraction hierarchy: abstract solutions, minimum edge weight, P-G to generated heuristics from the length of the solution path for those nodes visited during search, and reuse of heuristic information generated from previous searches. We also consider an approach which postpones the calculation of heuristics obtained by searching in the abstract space. This approach is referred to as Lazy Evaluation. Another of our objectives is to achieve more speed in search sacrificing optimality. For this we introduce a technique called Selective Method. Our last objective is to identify which abstraction method is the best for the search. We build abstraction hierarchies with different abstraction methods and we evaluate them using different search techniques: Classical Refinement (CR), Optimal Refinement (OR), and Alternating Opportunism (AO), and our variations of A$\sp{*}$.

This study discusses the generation of the minimum length checking sequences for FSM-based protocol conformance testing. The discussion focuses on finding the minimal length of resulting checking sequences for an FSM under different conditions. Without interleaving state identification and transition verification sequences, four methods (D-method, W-method, Wp-method and UIOv-method) of generating minimum length test sequences for FSM$\rm \sb{s}$ with reliable reset feature are reviewed and provided to construct checking sequences. These four methods are then improved to generate minimum length checking sequences for FSM$\rm \sb{s}$ without reliable reset feature and provided to construct checking sequences. Moreover, the effects of interleaving the state identification and transition verification sequences on the length of the checking sequences are studied. An algorithm for interleaving the state identification and transition verification sequences generated by the above four methods with reliable reset feature is proposed. It is observed that the reduction in the length of checking sequences due to interleaving is significant. Finally, the two general models for constructing minimal length checking sequences using distinguishing sequences with interleaved state identification and transition verification sequences are proposed. The proof for the first model to find a minimum length checking sequence in polynomial time is provided. The sequences generated by using both models are proved to be checking sequences. Examples are provided as applications of all the proposed methods and models.

After reading the book Combinatorics and Partially Ordered Sets written by W. T. Trotter, we wondered how much more effective an interactive version of this book would be. Using hypertext linking techniques a reader would get immediate access not only to the referenced index entry point, but to all referred to or linked information. Such a system would become even more powerful if the algorithms were not only explained in words, but available as interactive animations which could be played with. Algorithm animation is a form of program visualization that includes a number of specialized subareas that will be addressed in this thesis: In the first part of the thesis, we will address the issue of data structure visualization, for instance, the structure of partially ordered sets (Posets). We will describe methods for visualizing Posets in 2D and then motivate the need and the importance of providing three-dimensional representation of these structures and discuss how 3D graphics can provide additional information to the structure, while maximizing readability and visibility through the use of computations and metrics. In the second part we will focus on the area of the algorithm animation. We will introduce our model for abstracting the data, the operations and the semantics of computer programs, and the creation of graphical views of those abstractions. We will then, explain what is an interactive mapping (operation mapping) and their relations with input data and the algorithms, and finally we will present our system's architecture and discuss its components. We emphasize that the potential of such algorithm animation environment is great, but can be fully realized only if they are sufficiently easy, highly interactive, and enjoyable to use. This dissertation is a step toward achieving these goals.

The world is being inundated with knowledge at an ever-increasing rate. As intelligent beings and users of knowledge, we must find new ways to locate particular items of information in this huge reservoir of knowledge or we will soon be overwhelmed with enormous quantities of documents that no one any longer has time to read. The vast majority of knowledge is still being stored in conventional text written in natural language, such as books and articles, rather than in more "advanced" forms like knowledge bases. With more and more of these texts being stored on-line rather than solely in print, an opportunity exists to make use of the power of the computer to aid in the location and analysis of knowledge in on-line texts. We propose a tool to do this--the Text Analyzer. We have combined methods from computational linguistics and artificial intelligence to provide the users of the Text Analyzer with a variety of options for finding information in documents, verifying the consistency of this information, performing word and conceptual analyses and other operations. Parsing and indexing are not used in the Text Analyzer. The Text Analyzer can be connected to CODE4, a knowledge management system, so that a knowledge base can be constructed as knowledge is found in the text. We believe this tool will be especially useful for linguists, knowledge engineers, and document specialists.