In graph algorithms, we have done extensive and groundbreaking work on two fundamental classes of special graphs - planar graphs and interval graphs and their related graphs (such as circular arc graphs and circle graphs). We introduced a new data structure [2], PC-tree, which greatly simplifies the recognition of these two classes. Our new planarity test based on PC-trees is simple, elegant and indicates a way to obtain an optimal linear time algorithm for finding maximal planar subgraphs. Furthermore, PC-tree is a natural representation for planar graph embedding and PC-trees algorithms can unify the test of the consecutive ones property and the circular ones property.

        In DNA sequence analysis, we have produced an error-tolerant algorithm for the physical mapping and the clone assembly problem, which can accommodate the following four types of errors: 1. False positives, 2. False negatives, 3. Chimeric clones, 4. Non-unique probes. We have also used an iterative relaxation technique to develop an error-tolerant algorithm for the backbone assignment problem in NMR and a knowledge-based approach for protein secondary structure prediction. Finally, we have developed a knowledge-based algorithm to improve the neural net-based algorithm for the protein secondary structure prediction problem.

        In natural language processing we have designed a Chinese input system--GOING, which automatically translates a phonetic (or Pinyin) sequence into characters with a hit ratio close to 96%. It is widely used in Taiwan and received the Distinguished Chinese Information Product Award（中文傑出資訊產品獎）in 1993. In the PC Home software download area, GOING has been downloaded 830,000times. Within the top 20 download software, it is one of two types developed domestically. Another achievement is the development of a knowledge representation kernel, InfoMap, for the semantic analysis of natural language, which can be applied to a wide variety of application systems in natural language processing, biological knowledge base, automation of pipeline experiment, and e-learning. Our model for concept understanding can utilize heterogeneous knowledge representation systems. We have successfully developed an educational tutoring system that can understand and solve mathematics word problems of primary schools (grade 3).