Using an entropy argument, it is shown that stochastic context-free grammars (SCFG's) can model sources with hidden branching processes more efficiently than stochastic regular grammars (or equivalently HMM's). However, the automatic estimation of SCFG's using the Inside-Outside algorithm is limited in practice by its O(n3) complexity. In this paper, a novel pre-training algorithm is described which can give significant computational savings. Also, the need for controlling the way that non-terminals are allocated to hidden processes is discussed and a solution is presented in the form of a grammar minimization procedure.

ABSTRACT The Parsing and Learning System(PALS) is a massively parallel self-tuning context-free parser. It is capable of parsing sentences of unbounded length mainly due to its parse-tree representation scheme. The system is capable of improving its parsing performance through the presentation of training examples. INTRODUCTION Recent PDP research[Rumelhart et al.- 1986; Feldman and Ballard, 1982; Lippmann, 1987] involving natural language processtng[Fanty, 1988; Selman, 1985; Waltz and Pollack, 1985] have unrealistically restricted sentences to a fixed length. A solution to this problem was presented in the system CONPARSE[Charniak and Santos.

ABSTRACT The Parsing and Learning System(PALS) is a massively parallel self-tuning context-free parser. It is capable of parsing sentences of unbounded length mainly due to its parse-tree representation scheme. The system is capable of improving its parsing performance through the presentation of training examples. INTRODUCTION Recent PDP research[Rumelhart et al.- 1986; Feldman and Ballard, 1982; Lippmann, 1987] involving natural language processtng[Fanty, 1988; Selman, 1985; Waltz and Pollack, 1985] have unrealistically restricted sentences to a fixed length. A solution to this problem was presented in the system CONPARSE[Charniak and Santos.

ABSTRACT The Parsing and Learning System(PALS) is a massively parallel self-tuning context-free parser. It is capable of parsing sentences of unbounded length mainly due to its parse-tree representation scheme. The system is capable of improving its parsing performance through the presentation of training examples. INTRODUCTION Recent PDP research[Rumelhart et al.- 1986; Feldman and Ballard, 1982; Lippmann, 1987] involving natural language processtng[Fanty, 1988; Selman, 1985; Waltz and Pollack, 1985] have unrealistically restricted sentences to a fixed length. A solution to this problem was presented in the system CONPARSE[Charniak and Santos.

The automatic interpretation of natural language (in this work, English), database questions formulated by a user untrained in the technical aspects of database querying is an established problem in the field of artificial intelligence. State-of-the-art approaches involve the analysis of queries with syntactic and semantic grammars expressed in phrase structure grammar or transition network formalisms. With such method difficulties exist with the detection and resolution of ambiguity, with the misinterpretation possibilities inherent with finite length look-ahead, and with the modification and extension of a mechanism for other sources of semantic knowledge. This work examines the potential of optimization techniques tomore » solve these problems and interpret natural language, database queries. The proposed method involves developing a 0-1 integer programming problem for each query.

An important issue in achieving acceptance of computer systems used by the nonprogramming community is the ability to communicate with these systems in natural language. Often, a great deal of time in the design of any such system is devoted to the natural language front end. An obvious way to simplify this task is to provide a portable natural language front-end tool or facility that is sophisticated enough to allow for a reasonable variety of input; allows modification; and, yet, is easy to use. It allows for user input to be in sentence or nonsentence form or both, provides a detailed parse tree that the user can access, and also provides the facility to generate responses and save information.

An important issue in achieving acceptance of computer systems used by the nonprogramming community is the ability to communicate with these systems in natural language. Often, a great deal of time in the design of any such system is devoted to the natural language front end. An obvious way to simplify this task is to provide a portable natural language front-end tool or facility that is sophisticated enough to allow for a reasonable variety of input; allows modification; and, yet, is easy to use. This paper describes such a tool that is based on augmented transition networks (ATNs). It allows for user input to be in sentence or nonsentence form or both, provides a detailed parse tree that the user can access, and also provides the facility to generate responses and save information. The system provides a set of ATNs or allows the user to construct ATNs using system utilities. The system is written in Franz Lisp and was developed on a DEC VAX 11/780 running the ULTRIX-32 operating system.

This report describes recent and continuing research in artificial intelligence and related fields being conducted at the University of Pennsylvania. Although AI research takes place primarily in the Department of Computer and Information Science ( in School of Engineering and Applied Science), many aspects of this research are preformed in collaboration with other engineering departments as well as other schools at the University, such as the College of Arts and Sciences, the School of Medicine, and Wharton School.

About a year ago. I was approached by Phoebe Huang of Comtex Scientific Corporation who hoped that I would help devise a dramatically expanded index for topics in AI to aid Comtex in indexing the series of AI memos and reports that they had been gathering. Comtex had tried to get the ACM to expand and update its classification. But was told that ACM had just revised the listing two years ago or so ago, and did not intend to revise it again for a while: even if they did. The revision might require a year or more to complete. Comtex wanted the new classification within six to eight weeks. I agreed to take on the task, thinking it wouldn't be too hard. The major decision I had to make was whether to use the existing ACM index scheme and add to it, or start with a fresh sheet of paper and devise my own. I decided to stick with ACM's top two levels, only adding, not modifying, major headings.

In the past twenty years, much time, effort, and money has been expended on designing an unambiguous representation of natural language to make them accessible to computer processing, These efforts have centered around creating schemata designed to parallel logical relations with relations expressed by the syntax and semantics of natural languages, which are clearly cumbersome and ambiguous in their function as vehicles for the transmission of logical data. Understandably, there is a widespread belief that natural languages are unsuitable for the transmission of many ideas that artificial languages can render with great precision and mathematical rigor. But this dichotomy, which has served as a premise underlying much work in the areas of linguistics and artificial intelligence, is a false one. There is at least one language, Sanskrit, which for the duration of almost 1000 years was a living spoken language with a considerable literature of its own. Besides works of literary value, there was a long philosophical and grammatical tradition that has continued to exist with undiminished vigor until the present century. Among the accomplishments of the grammarians can be reckoned a method for paraphrasing Sanskrit in a manner that is identical not only in essence but in form with current work in Artificial Intelligence. This article demonstrates that a natural language can serve as an artificial language also, and that much work in AI has been reinventing a wheel millenia old. First, a typical Knowledge Representation Scheme (using Semantic Nets) will be laid out, followed by an outline of the method used by the ancient Indian grammarians to analyze sentences unambiguously. Finally, the clear parallelism between the two will be demonstrated, and the theoretical implications of this equivalence will be given.