System and process for grammatical inference
First Claim
1. A non-transitory computer-readable non-volatile storage medium having stored thereon computer-executable instructions that, when executed by one or more processors of a computer system, cause the computer system to perform a process for inferring a grammar from a plurality of example sentences, the process including:
- selecting ones of said example sentences having a common suffix or prefix component;
identifying the other of said suffix or prefix component of each selected sentence;
generating rules for generating the example sentences and the other components of the selected sentences, each of the rules having a left-hand side and a right-hand side;
reducing the right hand side of each rule on the basis of the right hand sides of the other rules using typed leftmost reduction or typed rightmost reduction;
identifying one or more shortest prefix components common only to negative example sentences of said plurality of example sentences;
generating rules for generating said one or more shortest prefix components;
removing one or more of said one or more shortest prefix components by removing one or more of said rules; and
generating a grammar on the basis of the reduced rules.
1 Assignment
0 Petitions
Accused Products
Abstract
A grammatical inference system for inferring a grammar from a plurality of example sentences. The system selects sentences having a common suffix or prefix component; identifies the other of said suffix or prefix component of each selected sentence; generating rules for generating the example sentences and the other components; reduces the right hand side of each rule on the basis of the right hand sides of the other rules; and generates a grammar on the basis of the reduced rules.
57 Citations
23 Claims
-
1. A non-transitory computer-readable non-volatile storage medium having stored thereon computer-executable instructions that, when executed by one or more processors of a computer system, cause the computer system to perform a process for inferring a grammar from a plurality of example sentences, the process including:
-
selecting ones of said example sentences having a common suffix or prefix component; identifying the other of said suffix or prefix component of each selected sentence; generating rules for generating the example sentences and the other components of the selected sentences, each of the rules having a left-hand side and a right-hand side; reducing the right hand side of each rule on the basis of the right hand sides of the other rules using typed leftmost reduction or typed rightmost reduction; identifying one or more shortest prefix components common only to negative example sentences of said plurality of example sentences; generating rules for generating said one or more shortest prefix components; removing one or more of said one or more shortest prefix components by removing one or more of said rules; and generating a grammar on the basis of the reduced rules. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A non-transitory computer-readable non-volatile storage medium having stored thereon computer-executable instructions that, when executed by one or more processors of a computer system, cause the computer system to perform a process for inferring a grammar from a plurality of positive and negative example sentences and a starting grammar, the process including:
-
identifying one or more shortest prefix components common only to said plurality of negative example sentences; identifying rules of the starting grammar for generating said one or more shortest prefix components; removing one or more of said one or more shortest prefix components by removing one or more of said rules; and generating a grammar on the basis of the remaining rules. - View Dependent Claims (15, 16, 17)
-
-
18. A grammatical inference system, including a memory storing sentences having suffix and prefix components and at least one processor programmed to perform a process for inferring a grammar from a plurality of positive and negative example sentences and a starting grammar, the process including:
-
selecting ones of said stored sentences having a common suffix or prefix component; identifying the other of said suffix or prefix component of each selected sentence; generating rules for generating the example sentences and the other components of the selected sentences, each of the rules having a left-hand side and right-hand side; reducing the right hand side of each rule on the basis of the right hand sides of the other rules using typed leftmost reduction or typed rightmost reduction; identifying one or more shortest prefix components common only to negative example sentences of said plurality of example sentences; generating rules for generating said one or more shortest prefix components; removing one or more of said one or more shortest prefix components by removing one or more of said rules; and generating a grammar on the basis of the reduced rules. - View Dependent Claims (19, 20, 21, 22, 23)
-
Specification