Common Heuristics for Parsing, Generation, and Whatever...

COMMON HEURISTICS FOR PARSING, GENERATION, AND WHATEVER... HASIDA. K6iti Ir/stitute for New Generation Computer Technology (ICOT) Mita Kokusai Bldg. 21F. 1-4-28 Mita, Minato-ku, Tokyo 108 JAPAN Tel: -4-81-3-3456-3069, E-mail: hasida@icot.or.jp ABSTRACT This paper discussers general hem'istics to control computation on symbolic constraints represented in terms of first-order logic programs. These heuristics are totally independen! of specific domains and tasks. Efficient computation for sentence parsing and genera- tion naturally emerge fi'om these heuristics, capturing the essence of standar d parsing procedures and seman- tic head-driven generat:ion. Thus. the same representa- tion of knowledge, inclfiding grammar and lexicon, can be exploited in a multi-directional manner in various aspects of language use. r 1 Introduction One lesson to learn from the repeated failure to design large AI systems in general is that the information flow in the cognitive systems is too complex and diverse to stipulate in the design of these AI systems. To capture this diversity of information flow. therefore. At systeins must be designed at a more abstract level where direc- tion of information flow is not explicit,. This is where constrai~t paradigm comes in. Since constraints do not stipulate the direction of informa- tion flow or processing Order, constraint-based systems could be tailored to halve tractable complexity, unlike procedural systems, which stipulate information flow and thus quickly become too colnplex for human de- signers to extend or maintain. Naturally, the key issue in the constraint-based ap- proach is how to control information flow. A very gen- eral control schema independent of any specific domain or task is vitally Ile('essal'y for the success of this ap- proach. The present paper introduces a system of constraint in a [o,-m of logic progi'am, and a set of very general heuristics to control symbolic operation on the con- straints. The sS'mboli( I operations herr are r('gar(h'd as Iransforming logic programs. "lhcv are quite per- missivr operations as a whole, allowing very diverse information processing involving top-down, bottom-up and other directions of informal ion flow. The heuristics control this computation so that only relevant infor- mation should be exploited and the resuhing represen- tation should be compact. Parsing and generation of sentences are shown to be efficiently done under these heuristics, and a standard parsing algorithm and the semantic head-driven generation [8] naturally emerge thereof. The rest of the paper is organized as follows. Sec- tion 2 describes the syntax of our system of constraint. Section 3 defines the symbolic computation on these constraints, and proposes a set of general heuristics to control computation. Section 4 and Section 5 show how sentence parsing and generation are executed effi- ciently by those heuristics. Finally, Section 6 concludes the paper. 8.1. 2 Constraint Network A program is a set of clauses. A clause is a set of lit- erals. A literal is an atomic constraint with a sign in front, of it. The sign is a '+', '-', or nil. A literal with a sign '+' or nil is called a positive literal and one with a …

Content truncated to 500 words