International Journal on Artificial Intelligence Tools

Within the framework of a project yielding to the development of an interactive spelling checking/correction system for Modern Greek (M.G.) to run on MS-DOS based computers, our team comprised of several computer engineers and linguists, undertook the following preliminary tasks: The examination and evaluation of pertinent existing research/work from both the computer engineering and linguistic fields, and conducted supplementary research deemed necessary for the purposes of the project. The overall objectives focused on the development of a system that would be convenient to run and use. Unlike similar current systems however, emphasis was given to optimal engineering quality and performance and moreover, optimal linguistic performance attained through substantial linguistic expertise backing.

Computer vision includes a variety of tasks of different natures, and there are many applications that have a strong need for knowledge representation and use. Typical knowledge representation methods used in computer vision include frames, rules, logic, constraints, and attributed prototype graphs. Although the advantages of hybrid approaches to knowledge representation have been recognized, no hybrid tool for high-level computer vision is available yet.

In this paper we first present a general framework for a hybrid knowledge representation tool. It is based on object-oriented programming and offers distinctive features such as high flexibility, coherence, and a clean integration of a collection of knowledge-based techniques. Then we give a brief overview of our computer vision tool VISTO, which was created along the framework discussed in the first part of the paper. With an application example we illustrate the use of VISTO and the advantages of hybrid knowledge representation in comparison to non-hybrid approaches.

Concept learning from examples in first-order languages has been widely studied recently. Specifically, many systems that integrate inductive learning and explanation-based learning have been proposed. However, concept learning is only a subproblem of the problem of knowledge base (which is referred to as a theory in first-order logic) revision. This is mainly because concept learning methods utilize background knowledge without regard to whether the knowledge is perfect or imperfect, while a knowledge base revision system should revise the knowledge base to be consistent with all environmental changes.

This paper presents a real theory revision method that guarantees the revised theory to be correct on all given examples. As a consequence, the problem of concept learning is also solved through the proposed method.

The proposed method is a two-phase approach. In the first phase, the input theory is generalized to cover all positive examples. Theoretically, this can be done by existing concept learning systems. The second phase then specializes the theory to exclude negative examples. The specialization must not cause excessive exclusion of covered positive examples. The paper focuses on designing such a specialization algorithm. Experimental results show that the proposed algorithm can mitigate the over-specialization problem.

In this paper, we study the performance of various IDA*-style searches and investigate methods to improve their performance by predicting in each stage the threshold to be used for pruning. Without loss of generality, we consider minimization problems in this paper. We first present three models to approximate the distribution of the number of search nodes by lower bounds: exponential, geometric, and linear, and illustrate these distributions based on some well-known combinatorial search problems. Based on these distributions, we show the performance of an ideal IDA* algorithm and identify reasons why existing IDA*-style algorithms perform well. In practice, we will be able to know from experience the type of distribution for a given problem instance, but will not be able to know the parameters of this distribution until the instance is solved. Hence, we develop RIDA*, a method that estimates dynamically the parameters of the distribution, and predicts the best threshold to be used in each stage. Finally, we compare the performance of several IDA*-style algorithms—Korf’s IDA* and RBFS, RIDA*, IDA*_CR and DFS*—on several application problems, and identify conditions under which each of these algorithms will perform well.

This paper extends an object-oriented approach to query processing in a deductive database with the consideration of deductive rules. In the object-oriented approach, each deductive rule and fact is represented as an active object, which acts with its own dedicated control sequences according to its functionality. All operations in objects are proceeded asynchronously. Since no object has global knowledge about the database, cooperation among objects is necessary in answering a query. While most of the conventional search strategies focus on some parts of the AND/OR tree expanded by a query at a time, the object-oriented approach can search down the AND/OR tree with a breadth-first strategy in parallel. As a result, all parts of the tree can be considered globally so that queries do not have to be evaluated in a tuple-by-tuple, operation-by-operation fashion; and the need of maintaining temporary relations can be eliminated.

This paper discusses the development of natural language interfaces to interactive computer systems using the NALIGE user interface management system. The task of engineering such interfaces is reduced to producing a set of well-formed specifications which describe lexical, syntactic, semantic, and pragmatic aspects of the selected application domain. These specifications are converted by NALIGE to an autonomous natural language interface that exhibits the prescribed linguistic and functional behavior. Development of several applications is presented to demonstrate how NALIGE and the associated development methodology may facilitate the design and implementation of practical natural language interfaces. This includes a natural language interface to Unix and its subsequent porting to MS-DOS, VAX/VMS, and VM/CMS; a natural language interface for Internet navigation and resource location; a natural language interface for text pattern matching; a natural language interface for text editing; and a natural language interface for electronic mail management. Additionally, design issues and considerations are identified/addressed, such as reuse and portability, content coupling, morphological processing, scalability, and habitability.