US5544262A — Method and apparatus for processing graphically i…

Claim 1

Independent Claim 231 words

A method for processing handwritten equations on a computer system comprising the steps of: receiving an input pattern comprising an equation which was derived from user handwritten strokes on a graphical user input device; parsing said input pattern utilizing a defined constrained attribute grammar to determine if said input pattern defines a valid pattern within said constrained attribute grammar, said valid pattern including a set of subpatterns satisfying constraints of production rules included in said constrained attribute grammar, said constraints being used by said parsing step to establish correspondence between said subpatterns and said production rules, said constraints including keywords to be identified within said subpatterns; providing a parsed tree from said step of parsing said input pattern when said input pattern is determined to be a valid pattern in said parsing step; deriving and displaying said equation and a result of said equation utilizing said parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree, wherein said receiving, parsing, providing, and deriving steps are performed on said computer system; detecting an edit made to said displayed equation having said result; and editing said parsed tree associated with said equation in response to said edit made to said displayed equation and without changing a structure of said parsed tree when said edit changes only a value or an operator of said equation.

Claim 2

Independent Claim 231 words

A method for processing handwritten equations on a computer system comprising the steps of: receiving an input pattern comprising an equation which was derived from user handwritten strokes on a graphical user input device; parsing said input pattern utilizing a defined constrained attribute grammar to determine if said input pattern defines a valid pattern within said constrained attribute grammar, said valid pattern including a set of subpatterns satisfying constraints of production rules included in said constrained attribute grammar, said constraints being used by said parsing step to establish correspondence between said subpatterns and said production rules, said constraints including keywords to be identified within said subpatterns; providing a parsed tree from said step of parsing said input pattern when said input pattern is determined to be a valid pattern in said parsing step; deriving and displaying said equation and a result of said equation utilizing said parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree, wherein said receiving, parsing, providing, and deriving steps are performed on said computer system; detecting an edit made to said displayed equation having said result; and editing said parsed tree associated with said equation in response to said edit made to said displayed equation and without changing a structure of said parsed tree when said edit changes only a value or an operator of said equation.

Claim 3

Dependent Claim 17 words

A method as recited in claim 1 wherein said graphical user input device comprises a tablet means.

Claim 4

Dependent Claim 17 words

A method as recited in claim 2 wherein said tablet means comprises a touch sensitive screen assembly.

Claim 5

Dependent Claim 19 words

A method as recited in claim 3 further comprising the step of displaying said result on said screen assembly.

Claim 6

Dependent Claim 31 words

A method as recited in claim 1 wherein said input pattern includes a plurality of stroke units which were derived from said user input strokes on said graphical user input device.

Claim 7

Dependent Claim 92 words

A method as recited in claim 1 wherein said step of parsing said input pattern comprises: a) identifying a subpattern of said input pattern that can be rewritten as a nonterminal symbol of a grammar of a predefined language; b) rewriting said subpattern as said nonterminal symbol; and c) determining if one of said production rules of said grammar exists where a start symbol of said grammar produces said nonterminal symbol, wherein said production rule includes a syntactic part, a semantic part, a constraints part including said constraints, and an action part.

Claim 8

Dependent Claim 112 words

A method as recited in claim 6 wherein said nonterminal symbol comprises at least one of said keywords and identifiers, and wherein said step of identifying a subpattern further comprises the steps of: a) determining that a subpattern in said pattern matches one of said keywords; b) identifying one of said production rules that corresponds to said keyword; c) identifying said subpattern that satisfies a first constraint of said production rule, said first constraint having a corresponding nonterminal symbol N; d) determining that said subpattern contains only one symbol X; and e) determining that a production rule exists wherein said syntactic part and said nonterminal rule symbol N produces said symbol X.

Claim 9

Dependent Claim 40 words

A method as recited in claim 6 wherein said step of identifying a subpattern further comprises a step of determining that a subpattern in said input pattern satisfies a spatial constraint relative to a different subpattern in said input pattern.

Claim 10

Dependent Claim 30 words

A method as recited in claim 8 wherein said step of determining that a subpattern satisfies a spatial constraint includes determining that a subpattern has multi-dimensional relationships with different subpatterns.

Claim 11

Dependent Claim 43 words

A method as recited in claim 1 wherein said step of identifying a subpattern further comprises examining a relevance measure of each of said keywords to determine the relevance of said keywords and the order of keywords to be matched to said subpattern.

Claim 12

Dependent Claim 27 words

A method as recited in claim 1 wherein said editing step includes substituting a changed value or a changed operator into said structure of said parsed tree.

Claim 13

Dependent Claim 39 words

A method as recited in claim 1 further comprising deriving and displaying a result of said equation utilizing said edited parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree.

Claim 14

Independent Claim 241 words

A system for processing handwritten equations comprising: digital processing means; screen means coupled to said digital processing means, said screen means being operative to display images in response to signals from said digital processing means and to transmit stroke signals to said digital processing means in response to the movement of a stylus means across said screen means; equation recognition means responsive to said stroke signals and operative to detect valid equations formed on said screen means, said equation recognition means including: means for parsing said equation to form a parsed tree, said means for parsing utilizing a constrained attribute grammar including a set of production rules, wherein said stroke signals are input to said means for parsing as a pattern including a set of subpatterns, and means for detecting whether a valid parsed tree has been formed by checking when said set of subpatterns can be rewritten as a start symbol according to said production rules and constraints included within said production rules, said constraints including keywords to be identified in said subpatterns; equation solving means operative to provide a result for said valid equations from said valid parsed tree; means for displaying said equation and said result on said screen proximate to said equation; and editing means for detecting an edit to said displayed equation and for editing said parsed tree in response to said edit to said displayed equation and without changing a structure of said parsed tree.

Claim 15

Independent Claim 241 words

A system for processing handwritten equations comprising: digital processing means; screen means coupled to said digital processing means, said screen means being operative to display images in response to signals from said digital processing means and to transmit stroke signals to said digital processing means in response to the movement of a stylus means across said screen means; equation recognition means responsive to said stroke signals and operative to detect valid equations formed on said screen means, said equation recognition means including: means for parsing said equation to form a parsed tree, said means for parsing utilizing a constrained attribute grammar including a set of production rules, wherein said stroke signals are input to said means for parsing as a pattern including a set of subpatterns, and means for detecting whether a valid parsed tree has been formed by checking when said set of subpatterns can be rewritten as a start symbol according to said production rules and constraints included within said production rules, said constraints including keywords to be identified in said subpatterns; equation solving means operative to provide a result for said valid equations from said valid parsed tree; means for displaying said equation and said result on said screen proximate to said equation; and editing means for detecting an edit to said displayed equation and for editing said parsed tree in response to said edit to said displayed equation and without changing a structure of said parsed tree.

Claim 16

Dependent Claim 63 words

A system as recited in claim 13 wherein said editing means comprises: means for detecting an edit made to an equation displayed upon said screen means having a valid parsed tree; means for determining whether said edit changes the structure of said parsed tree; and means for editing said parsed tree if said edit does not change the structure of said parsed tree.

Claim 17

Dependent Claim 36 words

A system as recited in claim 14 wherein said means for determining comprises means for determining that the parsed tree is not changed if said edit changes only a value or an operator of said equation.

Claim 18

Dependent Claim 33 words

A system as recited in claim 15 wherein said means for editing said parsed tree comprises means for substituting a changed value or a changed operator into said structure of said parsed tree.

Claim 19

Dependent Claim 226 words

A computer system for processing handwritten equations comprising: a) means for receiving an input pattern comprising an equation which was derived from user handwritten strokes on an input tablet; b) a parser for parsing said input pattern, said parser including: i) means for recognizing said input pattern as a valid pattern utilizing a defined constrained attribute grammar, said grammar including a set of production rules and a grammar start symbol, wherein said means for recognizing determines when said input pattern is valid by determining when said set of input subpatterns can be rewritten as said start symbol according to said set of production rules, wherein said production rules include a syntactic part, a semantic part, a constraints part, and an action part, said constraints part including spatial constraints that require predetermined spatial relationships be satisfied between said input subpatterns; and ii) means for providing a parsed tree when said means for recognizing recognizes said input pattern as a valid pattern; c) data manipulation means for deriving a result of said equation utilizing said parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree; and d) editing means for detecting an edit to said equation and for editing said parsed tree in response to said edit to said equation and without changing a structure of said parsed tree.

Claim 20

Dependent Claim 226 words

A computer system for processing handwritten equations comprising: a) means for receiving an input pattern comprising an equation which was derived from user handwritten strokes on an input tablet; b) a parser for parsing said input pattern, said parser including: i) means for recognizing said input pattern as a valid pattern utilizing a defined constrained attribute grammar, said grammar including a set of production rules and a grammar start symbol, wherein said means for recognizing determines when said input pattern is valid by determining when said set of input subpatterns can be rewritten as said start symbol according to said set of production rules, wherein said production rules include a syntactic part, a semantic part, a constraints part, and an action part, said constraints part including spatial constraints that require predetermined spatial relationships be satisfied between said input subpatterns; and ii) means for providing a parsed tree when said means for recognizing recognizes said input pattern as a valid pattern; c) data manipulation means for deriving a result of said equation utilizing said parsed tree by executing an operator at nodes of said parsed tree using operands included in said parsed tree; and d) editing means for detecting an edit to said equation and for editing said parsed tree in response to said edit to said equation and without changing a structure of said parsed tree.

Claim 21

Dependent Claim 31 words

A computer system as recited in claim 17 further comprising a display screen for displaying said result on said screen assembly and wherein said tablet comprises a touch sensitive screen assembly.

Claim 22

Dependent Claim 48 words

A computer system as recited in claim 18 wherein said production rules include constraints for identifying keywords and non-keywords within said input subpatterns and relevance measures for said keywords for matching said keywords to said input subpatterns in an order based on the relevance measures of said keywords.

Claim 23

Dependent Claim 106 words

A computer system as recited in claim 19 wherein said parser includes: a) means for determining that one of a plurality of subpatterns in said pattern matches one of said keywords; b) means for identifying a production rule that corresponds to said keyword; c) means for identifying said subpattern that satisfies a first constraint of said production rule, said first constraint having a corresponding nonterminal symbol N; d) means for determining that said subpattern contains only one symbol X; and e) means for determining that a production rule exists wherein said syntactic part of said production rule and said nonterminal symbol N produces said symbol X.

Claim 24

Dependent Claim 64 words

A computer system as recited in claim 20 wherein said editing means includes: means for detecting an edit made to an equation displayed upon said display screen having a valid parsed tree; means for determining whether said edit changes the structure of said parsed tree; and means for editing said parsed tree if said edit does not change the structure of said parsed tree.

Claim 25

Dependent Claim 74 words

A computer system as recited in claim 21 wherein said means for determining whether said edit changes the structure of said parsed tree comprises means for determining that the parsed tree is not changed if said edit changes only a value or an operator of said equation, and wherein said means for editing said parsed tree comprises means for substituting a changed value or a changed operator into said structure of said parsed tree.

Claim 26

Dependent Claim 82 words

A computer system as recited in claim 21 wherein said parser is included in a recognition domain, and said computer system further comprises a plurality of recognition domains, each including a parser, said recognition domains including: a strokes recognition domain; a word recognition domain coupled to an output of said strokes recognition domain; a math symbols recognition domain coupled to an output of said word recognition domain; and a calculation recognition domain coupled to an output of said math symbols recognition domain.

Claim 27

Dependent Claim 34 words

A method as recited in claim 17 wherein said step of determining that one of said subpatterns satisfies a spatial constraint includes determining that one of said subpatterns has multi-dimensional relationships with different subpatterns.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1999-08-06	2000-02-05	2000-08-06	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2003-08-06	2004-02-05	2004-08-06	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2007-08-06	2008-02-05	2008-08-06	$7700.00	Window Closed / Lapsed

Method and apparatus for processing graphically input equations

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag