Provided by Cognitive Sciences ePrint Archive
Working with Constrained Systems:
A Review of A. K. Joshi’s IJCAI-97 Research Excellence Award Acceptance Lecture1
Joseph S. Fulda
The search for artificial intelligence in machines might be thought of as the search for
the most general and powerful computational mechanisms, perhaps Turing’s O-
machines or predicate logic with relations, predicate variables, branching quantifiers,
and even, perhaps, quantifier variables, and the like. Yet much of Joshi’s successful
work in AI—he cites five areas and details three of them—has not used general
computational mechanisms. On the contrary, he has found that constrained formal-
computational systems are often most helpful. These constrained systems are
helpful because the constraints on the system may mirror the constraints of the
problem.
Joshi considers natural language processing. Ideally, we would want not a universal
mechanism whose constraints are all stipulated and include both the constraints of
(all) language as well as the constraints of a (particular) language, but a restricted
mechanism which builds in the constraints general to language so that all that
requires stipulation are the language-specific constraints. Such a restricted
mechanism will be a language template, a generator of the family of languages, and
its excellence will be in the fact that its structure already does much of the processing
required. Now there is not now available and Joshi says that there may never be
available such a general restricted mechanism for language. But he reviews areas
of his research which have solved part of the natural language processing complex
of problems using constrained systems.
The first area he reviews concerns some work he did in the late <50's using cascaded
finite state transducers for parsing. Suffice it to say that by now the use of finite state
machines for all kinds of parsing is standard—and much to be preferred over much
more complicated and general mechanisms. The second area he reviews concerns
work on lexicalized tree adjoining grammars, the recognition of syntactic and
semantic structure using a particular type of tree, grown with two operators,
substitution and adjoining. Again, the use of trees in syntactic and semantic analysis
of natural language is ubiquitous. The third area of his research that he reviews is
centering in discourse analysis. The basic idea is that every utterance in a discourse