Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Remarks
The Examiner acknowledges cancellation of claims 3 and 10, as well as amendments made to claims 1, 8, and 17.
In the Non-Final Office Action
The Examiner acknowledges and generally agrees with the short summary of rejections made in the previous Office Action.
35 U.S.C. 101
The Examiner acknowledges and has fully considered the applicant’s arguments.
The applicant seemingly summarizes, (Remarks page 8 – page 10 paragraph 1), portions of USPTO 35 U.S.C. 101 guidance.
The applicant seemingly references, (Remarks page 10 paragraph 2), the 35 U.S.C. 101 rejections made in the previous office action.
The applicant seemingly describes an example of an amended claim, (Remarks page 10 paragraphs 3-4), stating that the amended claims recite the combination of additional elements “generating a nondeterministic finite automata based on a regular expression pattern, wherein the step of generating the nondeterministic finite automata includes transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern and the Glushkov automata has no epsilon transitions.” The Examiner respectfully notes that in the recited limitations above, there are no additional elements (under the Alice Framework), nor a combination of additional elements.
The applicant continues, seemingly arguing, (Remarks page 10 paragraph 5 -page 11 paragraph 1), that the combination of these elements (referring to the elements of the limitations mentioned above), provides a technical solution to the technical problem of ReDoS attacks. The applicant continues, referencing the applicant’s specification describing the technical problem. The Examiner respectfully notes that the limitations referred to as a combination of elements that provide a technical solution, contain no additional elements under the Alice Framework.
The applicant continues, seemingly arguing, (Remarks page 11 paragraph 2), that the amended claims recite a specific technical architecture to address the technical problem, with the claims now requiring: “(1) generating the NFA by transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node corresponds to only one character and the Glushkov automata has no epsilon transitions—a specific NFA structure that abbreviates the multiple nodes appearing in a conventional Thompson automata (see specification at page 14, lines 4-6 and 14-16); (2) selectively applying a first matching algorithm or a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not; and (3) blocking the ReDoS attack through this combination of Glushkov NFA structure and hybrid algorithm selection.” The Examiner respectfully disagrees. The Examiner respectfully notes that the applicant’s specification, page 8 lines 17-23, show that regular expression patterns are described in mathematical relationships and formulas. Generating a nondeterministic finite automata based on a regular expression pattern, such as a Glushkov automata described in the specification, is transformed through mathematical formulas. See Glushkov, V. M. The abstract theory of automata, Russian Mathematical Surveys, volume 16, no. 5, oct 1961. The matching step described in the claim is done through a matching algorithm, which is considered mathematical relationships, see applicant’s specification, page 6 lines 1-2. Furthermore, the construction of an NFA is considered a mental process because it can be done with the human mind, or by a human using a pen and paper, see applicant’s drawings, figures 2- 10. Furthermore, the Examiner notes that “selectively applying a first matching algorithm or a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not;” recites a mental process, mathematical relationships and is part of mathematical formulas, as referenced in the Non-Final Office Action mailed on 03/02/2026 page 11, as well as can be found in the other prior Office Actions. Furthermore, the Examiner notes that the limitations regarding blocking the ReDoS attack are “wherein the matching step blocks a regular expression denial of service (ReDoS) attack”, of claim 1, “wherein the matching blocks a regular expression denial of service (ReDoS) attack”, of claim 8, and “thereby fundamentally blocking the ReDoS attack for both the extended regular expression and the regular expression”, of claim 17, are generally linking to a particular field of use, as referenced in the Non-Final Office Action mailed on 03/02/2026 page 12.
The applicant continues, seemingly arguing, (Remarks page 12 paragraph 1), that the claimed invention is similar to Desjardins, and provides a specific technical solution by implementing an automata processing apparatus that generates a specific type of NFA and applies a hybrid matching process that selectively applies the classical matching algorithm or the Spencer algorithm according to the regular expression pattern. The Examiner respectfully notes that the applicant is arguing for unclaimed elements. Furthermore, the Examiner respectfully points out, “an improvement in the abstract idea itself is not an improvement in technology”, see MPEP 2106.05(a)(II). The applicant continues, seemingly arguing that the applicant’s specification discusses the technical problem regarding ReDoS attacks, and that the claimed invention is a specific practical application that demonstrates an enhancement to the functioning of a computer-related technology and is not merely directed to an abstract idea. The Examiner respectfully disagrees. What the applicant has pointed out as “additional elements” above are not considered additional elements under the Alice Framework, but instead are directed towards a mental process, mathematical relationships, and mathematical formulas (as referenced above). Furthermore, the Examiner respectfully points out that “an improvement in the abstract idea itself is not an improvement in technology”, see MPEP 2106.05(a)(II).
The applicant continues, seemingly arguing, (Remarks page 12 paragraph 2), that the specification describes and demonstrates the technical improvement implemented by the claimed invention. The applicant continues, seemingly arguing that what is described in the applicant’s specification and in the applicant’s drawings represent specific technical implementations that improve the performance and security of regular expression engines, not merely abstract concepts that could be performed mentally or through manual methods. The Examiner respectfully disagrees. The Examiner respectfully points out that what the applicant has pointed out as “additional elements” above are not considered additional elements under the Alice Framework, but instead are directed towards a mental process, mathematical relationships, and mathematical formulas (as referenced above). Furthermore, the Examiner respectfully points out that “an improvement in the abstract idea itself is not an improvement in technology”, see MPEP 2106.05(a)(II). Furthermore, the Examiner respectfully points out that the creation of the NFA seemingly can be performed mentally or through manual methods, as shown in the applicant’s drawings of NFA in figures 2-10.
The applicant continues, seemingly arguing, (Remarks page 13 paragraph 1), that “even if the claims were directed to an abstract idea, the specific ordered combination of elements, particularly the generation of a Glushkov automata with no epsilon transitions where each node corresponds to only one character, combined with the selective application of a first matching algorithm for extended grammar patterns and a second matching algorithm for non-extended patterns, resulting in the blocking of ReDoS attacks—amounts to significantly more than the abstract idea itself.” The Examiner respectfully disagrees. The Examiner respectfully points out that what the applicant has pointed out as “additional elements” above are not considered additional elements under the Alice Framework, but instead are directed towards a mental process, mathematical relationships, and mathematical formulas (as referenced above). Furthermore, the Examiner respectfully points out that “an improvement in the abstract idea itself is not an improvement in technology”, see MPEP 2106.05(a)(II). The applicant continues, seemingly arguing that the combination provides an inventive concept that is not well-understood, routine, or conventional in the field. The Examiner respectfully points out that the Examiner has not stated that generation of the Glushkov automata nor selecting a matching algorithm is well understood, routine, or conventional activity besides, on page 13 paragraph 1 of the Non-Final Office Action mailed on 03/02/2026, the storing of an unselected state (as well understood, routine, conventional activity). The applicant continues, seemingly arguing that the claims do not merely recite generic computer components performing functions, seemingly arguing that they recite a specific arrangement of technical features (such as generation of a Glushkov NFA) that improve the functioning of the regular expression engine by preventing the exponential time complexity that causes ReDoS attacks. The Examiner respectfully disagrees, for at least the reasons stated in the Non-Final Office Action mailed on 03/02/2026, page 16 paragraph 1, regarding a computer on which the abstract idea is applied. Furthermore, the Examiner respectfully points out that what the applicant has pointed out as “additional elements” above are not considered additional elements under the Alice Framework, but instead are directed towards a mental process, mathematical relationships, and mathematical formulas (as referenced above). Furthermore, the Examiner respectfully points out that “an improvement in the abstract idea itself is not an improvement in technology”, see MPEP 2106.05(a)(II).
The applicant continues, seemingly arguing, (Remarks page 13 paragraphs 2-3) that the claims as a whole integrate any alleged judicial exception into a practical application and/or recite additional elements that amount to significantly more than the judicial exception. The Examiner respectfully disagrees for at least the reasons referenced above. Furthermore, see new reasons for rejection below due to amendments to the claims.
35 U.S.C. 112(b)
The Examiner acknowledges amendments to independent claims 1 and 8, the Examiner withdraws the 112(b) rejections due to the amendments. Furthermore, see new reasons for rejection below due to amendments to the claims.
35 U.S.C. 103
The Examiner acknowledges and has fully considered the applicant’s arguments.
The applicant seemingly recites the amended claim 1 (Remarks page 14 – page 15 paragraphs 1-4).
The applicant seemingly argues, (Remarks page 15 paragraph 5 – page 16 paragraph 1), that the prior art, Stewart et al. (U.S. Patent Application Publication 2013/0246324 A1), hereinafter “Stewart”, in view of Hron (Faculty of Information Technology CTU in Prague, Department of Theoretical Computer Science, Backreferences in practical regular expressions, Martin Hron, 27 May 2020), hereinafter “Hron”, and Tsay (U.S. Patent 8751466 B1), hereinafter “Tsay” does not teach or suggest every element of the claimed invention. The Examiner respectfully notes that, regarding claim 1 (and claim 3), the Examiner did not rely on Stewart in view of Hron and Tsay, but instead relied upon Hron in view of Tsay. The Examiner notes that the applicant states, (Remarks page 14 paragraph 4), “Elements of claim 3 have been incorporated into claim 1.” The Examiner respectfully disagrees (that the prior art does not teach or suggest every element of the claimed invention) for at least the same reasons as referenced in the prior Non-Final Office Action mailed on 03/02/2026, pages 17-22 regarding claim 1, and claim 3.
The applicant further seemingly argues, (Remarks page 16 paragraph 2) that though Hron mentions Glushkov construction, it does not teach or suggest the claimed limitation of generating a Glushkov automata such that each node corresponds to only one character of the regular expression pattern and the automata has no epsilon transitions. The Examiner respectfully points out, as referenced in the footnotes on page 23 of the prior Non-Final Office Action mailed on 03/02/2026, Glushkov NFAs are known to be epsilon free, and each symbol being an NFA state. It is a defining feature of a Glushkov construction that each node corresponds to a character and that there are no epsilon transitions.
The applicant further seemingly argues, (Remarks page 16 paragraph 3) that Hron’s actual implementation is based on memory automata not Glushkov automata, and that Hron does not implement, test, or evaluate the Glushkov construction for any purpose. The applicant furthermore seemingly argues that Hron’s reference to Glushkov construction is limited to providing historical context for NFA construction methods, and defining the concept of deterministic regular expressions. The applicant furthermore seemingly argues that Hron does not teach generating a Glushkov automata with specific structural properties of each node corresponding to only one character and no epsilon transitions for use in checking an acceptance path for a character string. The applicant respectfully disagrees. The applicant respectfully points out, as referenced in the footnotes on page 23 of the prior Non-Final Office Action mailed on 03/02/2026, Glushkov NFAs are known to be epsilon free, and each symbol being an NFA state. It is a defining feature of a Glushkov construction that each node corresponds to a character and that there are no epsilon transitions. Furthermore, the Examiner respectfully points out, as shown in the Final Rejection Office Action dated 08/26/2025, Hron teaches different methods (which is mapped to the claimed methods in the Office Action) for different circumstances of regular expression matching.
The applicant further seemingly argues, (Remarks page 17 paragraph 1), that there is no motivation in Hron to modify its memory automata-based approach to instead use the Glushkov instruction. The Examiner respectfully notes, as referenced in the Non-final Office Action mailed on 03/02/2026 page 7 paragraph 3, and, as shown in the Final Rejection Office Action dated 08/26/2025, Hron teaches different methods (which is mapped to the claimed methods in the Office Action) for different circumstances of regular expression matching. The Examiner also respectfully notes that the Examiner has not suggested that Hron abandon one approach or another approach, but rather the Examiner relies upon Hron in simply teaching the claimed limitations, as referenced in the prior Office Actions. Furthermore, as referenced in the Non-final Office Action mailed on 03/02/2026 page 9 paragraph 2, the Examiner notes that it is an argument for unclaimed elements to suggest that the claimed limitations require no memory automata.
The applicant further seemingly argues, (Remarks page 17 paragraph 2), that Tsay does not cure the deficiencies of Hron, and that Tsay does not teach or suggest generating a Glushkov automata according to Glushkov construction such that each node corresponds to only one character and the automata has no epsilon transitions. The applicant further seemingly argues, (Remarks page 17 paragraphs 3-4), that Stewart does not remedy the deficiencies of Hron and Tsay. The Examiner respectfully notes that Hron is relied upon, in regards to claim 1, for Glushkov construction, as referenced above.
The applicant further seemingly argues, (Remarks page 17 paragraph 4), that claim 8 is a related independent claim (to claim 1) that is patentably distinguished over Stewart in view of Hron and Tsay for similar reasons as claim 1. The Examiner respectfully disagrees for at least the reasons listed above regarding claim 1.
Conclusion
The Examiner acknowledges the applicants conclusion statements.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1, 2, 8, 9, and 15-17 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 1, claim 1 recites the limitation of: “wherein the step of generating the nondeterministic finite automata includes transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern”. It is unclear if the limitation is meant to be understood as each node corresponds to only one of the characters in the regular expression (as in every node corresponds to the same singular character), or if it is meant to be understood as each node respectively corresponds to a singular character with character of the regular expression with each node not necessarily having to correspond to the same singular character of the regular expression.
Claims 2, and 15-17 inherit the same deficiency as claim 1 based on dependence.
Regarding claim 2, claim 2 recites the limitation of: “wherein the step of generating the nondeterministic finite automata includes transforming each node to correspond to a character of the character string”. Claim 2 is dependent on claim 1, and claim 1 recites the limitation of: “wherein the step of generating the nondeterministic finite automata includes transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern”. It is unclear if the “transforming each node to correspond to a character of the character string”, is meant to be the same as the limitation of: “each node of the Glushkov automata corresponds to only one character of the regular expression pattern”, or if the transformation of each node of claim 1 is meant to be replaced by “transforming each node to correspond to a character of the character string” of claim 2.
Claim 16 inherits the same deficiency as claim 2 based on dependence.
Regarding claim 8, claim 8 recites the limitations of: “generate the nondeterministic finite automata by transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern”. It is unclear if the limitation is meant to be understood as each node corresponds to only one of the characters in the regular expression (as in every node corresponds to the same singular character), or if it is meant to be understood as each node respectively corresponds to a singular character with character of the regular expression with each node not necessarily having to correspond to the same singular character of the regular expression.
Furthermore, claim 8 recites the limitations of: “a memory configured to store a program executed by the processor, wherein the processor is configured to execute the program to generate a nondeterministic finite automata”, and “wherein the processor is configured to generate the nondeterministic finite automata”. It is unclear if it is the program, or the processor itself, or the processor through executing the program that generates the nondeterministic finite automata.
Claim 9 inherits the same deficiency as claim 8 based on dependence.
Regarding claim 9, claim 9 recites the limitation of: “wherein the processor is further configured to execute the program to generate the nondeterministic finite automata by transforming each node to correspond to a character of the character string”. Claim 9 is dependent on claim 8, and claim 8 recites the limitation of: “generate the nondeterministic finite automata by transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern”. It is unclear if the “transforming each node to correspond to a character of the character string”, is meant to be the same as the limitation of: “each node of the Glushkov automata corresponds to only one character of the regular expression pattern”, or if the transformation of each node of claim 8 is meant to be replaced by “transforming each node to correspond to a character of the character string” of claim 9.
Furthermore, claim 9 recites the limitation of: “wherein the processor is further configured to execute the program to generate the nondeterministic finite automata”. Claim 8, which claim 9 is dependent upon recites the limitation of: “wherein the processor is configured to generate the nondeterministic finite automata”. It is unclear if, “wherein the processor is further configured to execute the program to generate the nondeterministic finite automata” of claim 9 is meant to be understood as the same as the limitation as claim 8 or replace the limitation of: “wherein the processor is configured to generate the nondeterministic finite automata” of claim 8.
Regarding claim 16, claim 16 recites the limitation of: “eliminate epsilon transitions”. Claim 16 is dependent on claim 1, and claim 1 recites the limitations of: “transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern”, and “and the Glushkov automata has no epsilon transitions”. It is unclear what epsilon transitions are eliminated in claim 16 since claim 1, which claim 16 is dependent upon, states that the regular expression is transformed into a Glushkov automata that has no epsilon transitions.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1, 2, 8, 9 and 15-17 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Regarding claim 1, under the Alice Framework Step 1, claim 1 falls within the four statutory categories of patentable subject matter identified by 35 USC 101: a process, machine, manufacture, or a composition of matter.
Under the Alice Framework Step 2A prong 1, claim 1 recites an abstract idea, including both a mental process and mathematical concept. Specifically, claim 1 recites the following mental process, mathematical relationships, and mathematical formulas:
a step of generating a nondeterministic finite automata based on a regular expression pattern, wherein the step of generating the nondeterministic finite automata includes transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern and the Glushkov automata has no epsilon transitions; and a matching step of checking an acceptance path for a character string with respect to the nondeterministic finite automata, wherein the regular expression pattern is expressed as a regular expression or an extended regular expression, and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof, wherein the matching step selects between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not, wherein in the matching step, the second matching algorithm is applied in response to the regular expression pattern not including the extended grammar so that all next states that move through each character starting from a starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every state in the set of current states, and updating the set of current states to reflect new states transitioned to, and when a current state includes an acceptance state at a time when all characters are consumed, it is determined that there is the acceptance path, wherein in the matching step, the first matching algorithm is applied in response to the regular expression pattern including the extended grammar so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, when there is an acceptance path among paths progressed in a state selected first, matching is terminated, and when the acceptance path is not searched, a new path is searched based on a most recently state and position.
Applicant’s specification, page 8 lines 17-23, show that regular expression patterns are described in mathematical relationships and formulas. Generating a nondeterministic finite automata based on a regular expression pattern, such as a Glushkov automata described in the specification, is transformed through mathematical formulas. See Glushkov, V. M. The abstract theory of automata, Russian Mathematical Surveys, volume 16, no. 5, oct 1961. The matching step described in the claim is done through a matching algorithm, which is considered mathematical relationships, see applicant’s specification, page 6 lines 1-2. Furthermore, the claim is considered a mental process because it can be done with the human mind, or by a human using a pen and paper, see applicant’s drawings, figures 2- 10.
It is noted that the Examiner does not give patentable weight to the preamble of claim 1 because deletion of the preamble phrase does not affect the steps of the claimed invention. See MPEP 2111.02 (II)(¶4).
Under the Alice Framework Step 2A prong 2 analysis, claim 1 recites an additional element of, “wherein the matching step blocks a regular expression denial of service (ReDoS) attack”. This additional element is merely generally linking to a particular field of use, see MPEP 2106.04(d). Furthermore, claim 1 recites an additional elements of, “an adjacent state to the current state is separately stored along with a position on the character string”, “stored”. Merely storing information, such as storing an adjacent state, comprise insignificant extra-solution activity. For these reasons, the claim is not integrated into a practical application.
Under the Step 2B analysis, for at least the reasons cited in the Step 2A prong 2 analysis, claim 1, when considered as a whole does not amount to significantly more than the abstract idea. The mere general linking to a particular field of use, “wherein the matching step blocks a regular expression denial of service (ReDoS) attack”, does not amount to significantly more than an abstract idea, see MPEP 2106.05(I)(A)(iv). Furthermore, the additional element of storing information, “an adjacent state to the current state is separately stored along with a position on the character string”, “stored”, comprise well understood, routine, and conventional activity. See MPEP 2106.05(d)(II)(iv). For these reasons, the claim does not amount to significantly more than the abstract idea.
Claim 2 is rejected for at least the reasons set forth with respect to claim 1. Claim 2 merely further limits the mental process and mathematical concept set forth in claim 1. Under the Alice Framework Step 2A prong 1, claim 2 recites an abstract idea, mathematical formulas. Specifically, claim 2 recites the following mental process, mathematical relationships, and mathematical formulas:
Wherein the step of generating the nondeterministic finite automata includes transforming each node to correspond to a character of the character string.
Claim 2 recites no further additional elements that would require further analysis under Step 2A prong 2 and Step 2B.
Claim 15 is rejected for at least the reasons set forth with respect to claim 1. Claim 15 merely further limits the mental process and mathematical concept set forth in claim 1. Under the Alice Framework Step 2A prong 1, claim 15 recites an abstract idea, mathematical formulas. Specifically, claim 15 recites the following mental process, mathematical relationships, and mathematical formulas:
wherein, in the second matching algorithm, all next states that move through each character starting from the starting state are simultaneously considered.
Under the Alice Framework Step 2A prong 2 analysis, claim 15 recites an additional element of, “so that an exponential increase in matching time is blocked”. This additional element is not a positively recited claim limitation, but is merely an intended result of the prior limitation. Furthermore, this additional element is merely a direct consequence of the abstract idea, not from an improved technology, see MPEP 2106.04(d)(1), MPEP 2111.04. For these reasons, the claim is not integrated into a practical application.
Under the Step 2B analysis, for at least the reasons cited in the Step 2A prong 2 analysis, claim 15, when considered as a whole does not amount to significantly more than the abstract idea. The additional element of “so that an exponential increase in matching time is blocked” is merely a direct consequence of the abstract idea, not from an improved technology, and thus does not amount to significantly more than an abstract idea, see MPEP 2106.05(a)(II) regarding “an improvement in the abstract idea itself is not an improvement in technology”.
Claim 16 is rejected for at least the reasons set forth with respect to claim 2. Claim 16 merely further limits the mental process and mathematical concept set forth in claim 2. Under the Alice Framework Step 2A prong 1, claim 16 recites an abstract idea, mathematical formulas. Specifically, claim 16 recites the following mental process, mathematical relationships, and mathematical formulas:
wherein the transforming each node includes transforming each node to correspond to only one character to eliminate epsilon transitions.
Claim 16 recites no further additional elements that would require further analysis under Step 2A prong 2 and Step 2B.
Claim 17 is rejected for at least the reasons set forth with respect to claim 1. Claim 17 merely further limits the mental process and mathematical concept set forth in claim 1. Under the Alice Framework Step 2A prong 1, claim 17 recites an abstract idea, mathematical formulas. Specifically, claim 17 recites the following mental process, mathematical relationships, and mathematical formulas:
wherein the selection between applying the first matching algorithm and the second matching algorithm in combination with the Glushkov automata.
Under the Alice Framework Step 2A prong 2 analysis, claim 17 recites an additional element of, “fundamentally blocking the ReDoS attack”. This additional element is merely generally linking to a particular field of use, see MPEP 2106.04(d). Furthermore, claim 1 recites an additional element of, “automata prevents exponential time growth in match confirmation time”. This additional element is merely an intended result of the prior limitations. Furthermore, this additional element is merely a direct consequence of the abstract idea, not from an improved technology, see MPEP 2106.04(d)(1), MPEP 2111.04. For these reasons, the claim is not integrated into a practical application.
Under the Step 2B analysis, for at least the reasons cited in the Step 2A prong 2 analysis, claim 1, when considered as a whole does not amount to significantly more than the abstract idea. The mere general linking to a particular field of use, “fundamentally blocking the ReDoS attack”, does not amount to significantly more than an abstract idea. See MPEP 2106.05(I)(A)(iv). Furthermore, the additional element of “prevents exponential time growth in match confirmation time” is merely a direct consequence of the abstract idea, not from an improved technology, and thus does not amount to significantly more than an abstract idea, see MPEP 2106.05(a)(II) regarding “an improvement in the abstract idea itself is not an improvement in technology”.
Regarding claim 8, under the Alice Framework Step 1, claim 8 falls within the four statutory categories of patentable subject matter identified by 35 USC 101: a process, machine, manufacture, or a composition of matter.
Under the Alice Framework Step 2A prong 1, claim 8 recites an abstract idea, including both a mental process and mathematical concept. Specifically, claim 8 recites the following mental process, mathematical relationships, and mathematical formulas:
generate a nondeterministic finite automata based on a regular expression pattern, and perform matching to check an acceptance path for a character string with respect to the nondeterministic finite automata, wherein the is configured to generate the nondeterministic finite automata by transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern and the Glushkov automata has no epsilon transitions, wherein the regular expression pattern is expressed as a regular expression or an extended regular expression, and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof, perform the matching by selecting between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not, apply the second matching algorithm in response to the regular expression pattern not including the extended grammar so that all next states that move through each character starting from a starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every state in the set of current states, and updating the set of current states to reflect new states transitioned to, and when a current state includes an acceptance state at a time when all characters are consumed, it is determined that there is the acceptance path, apply the first matching algorithm in response to the regular expression pattern including the extended grammar so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, when there is an acceptance path among paths progressed in a state selected first, matching is terminated, and when the acceptance path is not searched, a new path is searched based on a most recently state and position.
Applicant’s specification, page 8 lines 17-23, show that regular expression patterns are described in mathematical relationships and formulas. Generating a nondeterministic finite automata based on a regular expression pattern, such as a Glushkov automata described in the specification, is transformed through mathematical formulas. See Glushkov, V. M. The abstract theory of automata, Russian Mathematical Surveys, volume 16, no. 5, oct 1961. The matching step described in the claim is done through a matching algorithm, which is considered mathematical relationships, see applicant’s specification, page 6 lines 1-2. Furthermore, the claim is considered a mental process because it can be done with the human mind, or by a human using a pen and paper, see applicant’s drawings, figures 2- 10.
It is noted that the Examiner does not give patentable weight to the preamble of claim 8 because deletion of the preamble phrase does not affect the steps of the claimed invention. See MPEP 2111.02 (II)(¶4).
Under the Alice Framework Step 2A prong 2 analysis, claim 8 recites an additional elements of,
“processor”, “memory configured to store a program executed by the processor”, wherein the “processor is configured to execute the program”, “wherein the processor is further configured to execute the program”. The processor and memory are merely generally linked to the mental process, mathematical relationships, and mathematical calculations in a manner that merely “apply it” on a computer, see MPEP 2106.04(a)(2)(III)(C), MPEP 2106.04(d), 2106.05(f). Furthermore, the claim recites the additional element of “and wherein the matching blocks a regular expression denial of service (ReDoS) attack”. This additional element is merely generally linking to a particular field of use, see MPEP 2106.04(d). Furthermore, claim 8 recites an additional elements of, “an adjacent state to the current state is separately stored along with a position on the character string”, “stored”. Merely storing information, such as storing an adjacent state, comprise insignificant extra-solution activity. For these reasons, the claim is not integrated into a practical application.
Under the Step 2B analysis, for at least the reasons cited in the Step 2A prong 2 analysis, claim 8, when considered as a whole does not amount to significantly more than the abstract idea. The mere generally linking to the mental process, mathematical relationships, and mathematical calculations in a manner that merely “apply it” on a computer regarding limitations “processor”, “memory configured to store a program executed by the processor”, “wherein the processor is configured to execute the program”, “wherein the processor is further configured to execute the program”, does not amount to significantly more than the abstract idea, see MPEP 2106.05(I)(A)(i), 2106.05(f). The mere general linking to a particular field of use, “and wherein the matching blocks a regular expression denial of service (ReDoS) attack”, does not amount to significantly more than an abstract idea, see MPEP 2106.05(I)(A)(iv). Furthermore, the additional element of storing information, “an adjacent state to the current state is separately stored along with a position on the character string”, “stored”, comprise well understood, routine, and conventional activity. See MPEP 2106.05(d)(II)(iv). For these reasons, the claim does not amount to significantly more than the abstract idea.
Claim 9 is rejected for at least the reasons set forth with respect to claim 8. Claim 9 merely further limits the mental process and mathematical concept set forth in claim 8. Under the Alice Framework Step 2A prong 1, claim 9 recites an abstract idea, mathematical formulas. Specifically, claim 9 recites the following mental process, mathematical relationships, and mathematical formulas:
generate the nondeterministic finite automata by transforming each node to correspond to a character of the character string.
Claim 9 recites no further additional elements that would require further analysis under Step 2A prong 2 and Step 2B.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1, 2, and 15-17 are rejected under 35 U.S.C. 103 as being unpatentable over Hron, in view of Tsay.
With regards to claim 1, Hron teaches:
An automata processing method by an automata processing apparatus, the method comprising: (Section 3.1 ¶4 regarding a method for regular expression to nondeterministic finite automata transformation (NFA); 3.2 ¶1 and ¶2 regarding methods for searching and matching regular expressions in an NFA);
a step of generating a nondeterministic finite automata based on a regular expression pattern, (Section 3.2 ¶1 regarding constructing an NFA from a regular expression);
wherein the step of generating the nondeterministic finite automata includes transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern and the Glushkov automata has no epsilon transitions; (Fig. Section 3.1 ¶4 regarding Glushkov algorithm1 being an NFA construction algorithm2 to be used);
and a matching step of checking an acceptance path for a character string with respect to the nondeterministic finite automata, (Fig. 3.1 regarding a final state 6; Fig. 3.2 regarding a final state 6; Section 3.4 Example 3.2 regarding matching and finding a path to the final state 6);
wherein the regular expression pattern is expressed as a regular expression or an extended regular expression, (Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.3.2 ¶1 regarding supporting extended regular expression by including support for backreferences);
and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof, (Section 3.3.2 ¶1 regarding supporting extended regular expression by including support for backreferences; Section 3.3.2 ¶2 regarding additional support to other extensions including a look-ahead search, otherwise known as a forward search; Section 2.2.3 Definition 2.2 regarding inclusion of dereference support; Section 3.3.2 ¶1 regarding use of a capture group);
Wherein a first matching algorithm and a second matching algorithm according to whether the regular expression pattern corresponds to the extended regular expression or not (Section 3.2 ¶1 and ¶2 regarding different methods of regular expression matching; Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.2.2 regarding a backtracking method of matching especially good for extended regular expressions that support backreferences);
wherein in the matching step, the second matching algorithm is applied in response to the regular expression pattern not including the extended grammar (Section 3.2.3 ¶1 regarding NFA matching without backtracking working well for classical regular expressions);
so that all next states that move through each character starting from the starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every state in the set of current states, and updating the set of current states to reflect new states transitioned to, (Section 3.2.3 ¶1 regarding NFA matching without backtracking, updating based on all possible transitions; Section 5.1.3 Algorithm 2 regarding a matching algorithm searching all paths simultaneously3);
and when a current state includes an acceptance state at a time when all characters are consumed, it is determined that there is the acceptance path, (Section 5.1.1 ¶1 regarding how algorithm 2 starts at an initial state, and transverses the set of configurations until reaching an accepting, final, state);
wherein in the matching step, the first matching algorithm is applied in response to the regular expression pattern including the extended grammar (Section 3.3.2 ¶1 regarding supporting extended regular expression; Section 3.3 Algorithm 1 regarding a first algorithm utilizing backtracking for extended regular expressions; Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching);
so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, (Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching);
when there is an acceptance path among paths progressed in a state selected first, matching is terminated, (Section 3.4.1.1 Example 3.2 regarding an example showing the method of backtracking, and regular expression matching with an NFA until reaching the final state);
and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position. (Section 3.4.1.1 Example 3.2 regarding an example showing the method of backtracking, and regular expression matching with an NFA until reaching the final state);
Hron does not explicitly teach:
the matching step selects between applying
However, Hron does teach different methods of regular expression matching as referenced above. Hron also teaches that these different methods work well with particular regular expressions, such as matching without backtracking, as in classical matching, working well with classical regular expressions as referenced above. Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, because it would have been obvious to try. See MPEP 2141(III)(E). Furthermore, , it would have been obvious to one of ordinary skill in the art at the time the invention was made to combine these different methods of regex matching taught in Hron into a singular unit, the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, since it has been held that forming in one piece an article, which has formerly been formed in two pieces and put together, involves only routine skill in the art. Howard v. Detroit Stove Works, 150 U.S. 164 (1893).
Hron does not explicitly teach:
an adjacent state to the current state is separately stored along with a position on the character string,
However, Hron does teach backtracking if a match on a current path fails, and trying another path (Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching), this would imply that the not yet searched paths, along with a position on the character string, are stored in order to backtrack to them and continue matching. Hron further teaches, storing already visited paths (Section 3.3.1 ¶2 regarding storing previously visited configurations). Separately storing an already visited path, or state, is simply an inversion of separately storing an adjacent state. Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to try storing an adjacent state along with a position on the character string instead of the previously done inverse of storing paths previously visited, as taught by Hron, because it would have been obvious to try. See MPEP 2141 (III)(E).
Hron does not explicitly teach:
and wherein the matching step blocks a regular expression denial of service (ReDoS) attack.
However, Tsay teaches:
and wherein the matching step blocks a regular expression denial of service (ReDoS) attack. (Column 13 lines 41-44 regarding matching step of a regular expression engine designed to withstand ReDoS attacks)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Hron with the teaching of Tsay to withstand regular expression denial of service (ReDoS) attacks. [Tsay: Column 13 lines 43-44].
With regards to claim 2, Hron in view of Tsay teaches the automata processing method of claim 1, as referenced above.
Hron further teaches:
wherein the step of generating the nondeterministic finite automata includes transforming each node to correspond to a character of the character string. (Fig. 3.1; Fig. 3.2; Section 3.1 ¶4 regarding Glushkov algorithm being an NFA construction algorithm to be used).
With regards to claim 15, Hron in view of Tsay teaches the automata processing method of claim 1, as referenced above.
Hron further teaches:
wherein, in the second matching algorithm, all next states that move through each character starting from the starting state are simultaneously considered so that an exponential increase in matching time is blocked. (Section 3.2.3 ¶1 regarding NFA matching without backtracking, updating based on all possible transitions; Section 5.1.3 Algorithm 2 regarding a matching algorithm searching all paths simultaneously3; MPEP 2111.04(I) suggests that patentable weight not be given to a limitation that simply expresses the intended result of a process step positively recited. Regardless, the Examiner interprets the result, “so that an exponential increase in matching time is blocked” as a direct consequence of the prior limitation, thus mapping of the prior limitation, as shown above, would consequently result in the same manner).
With regards to claim 16, Hron in view of Tsay teaches the automata processing method of claim 2, as referenced above.
Hron further teaches:
wherein the transforming each node includes transforming each node to correspond to only one character to eliminate epsilon transitions. (Fig. Section 3.1 ¶4 regarding Glushkov1 algorithm2 being an NFA construction algorithm to be used).
With regards to claim 17, Hron in view of Tsay teaches the automata processing method of claim 1, as referenced above.
Hron further teaches:
wherein the first matching algorithm and the second matching algorithm in combination with the Glushkov automata prevents exponential time growth in match confirmation time. (Section 3.2 ¶1 and ¶2 regarding different methods of regular expression matching; Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.2.2 regarding a backtracking method of matching especially good for extended regular expressions that support backreferences; MPEP 2111.04(I) suggests that patentable weight not be given to a limitation that simply expresses the intended result of a process step positively recited. Regardless, the Examiner interprets the result, “prevents exponential time growth in match confirmation time” as a direct consequence of the prior limitation, thus mapping of the prior limitation, as shown above, would consequently result in the same manner).
Hron does not explicitly teach:
selection between applying
However, Hron does teach different methods of regular expression matching as referenced above. Hron also teaches that these different methods work well with particular regular expressions, such as matching without backtracking, as in classical matching, working well with classical regular expressions as referenced above. Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, because it would have been obvious to try. See MPEP 2141(III)(E). Furthermore, , it would have been obvious to one of ordinary skill in the art at the time the invention was made to combine these different methods of regex matching taught in Hron into a singular unit, the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, since it has been held that forming in one piece an article, which has formerly been formed in two pieces and put together, involves only routine skill in the art. Howard v. Detroit Stove Works, 150 U.S. 164 (1893).
Hron does not explicitly teach:
thereby fundamentally blocking the ReDoS attack for both the extended regular expression and the regular expression.
However, Tsay teaches:
thereby fundamentally blocking the ReDoS attack for both the extended regular expression and the regular expression. (Column 13 lines 41-44 regarding matching step of a regular expression engine designed to withstand ReDoS attacks)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Hron with the teaching of Tsay to withstand regular expression denial of service (ReDoS) attacks. [Tsay: Column 13 lines 43-44].
Claims 8-9 are rejected under 35 U.S.C. 103 as being unpatentable over Stewart, in view of Hron, and in further view of Tsay.
With regards to claim 8, Stewart teaches:
An automata processing apparatus, comprising: (Fig. 1; Fig. 4; ¶0016 regarding the description of the apparatus of figure 1 having components configured to execute an automaton);
a processor; and (Fig. 1 item 102; ¶0026 regarding inclusion of a processor);
a memory configured to store a program executed by the processor, (Fig. 1 items 102, and 104; ¶0026 regarding inclusion of a memory component; ¶0082 regarding storing instructions for the processor to execute);
wherein the processor is configured to execute the program to generate a nondeterministic finite automata based on a regular expression pattern, (¶0026 regarding a pattern analyzer component incorporating a processor and memory to generate an automaton; ¶0097 regarding the pattern analyzer generating the automaton corresponding to the patterns based on common symbols between patterns; Figs. 3, and 4; ¶0029 regarding the pattern analyzer generating automaton 300 (Fig. 3), and automaton 300 being a nondeterministic finite automaton; ¶0033 regarding Fig. 4 as a nondeterministic finite automaton);
and perform matching to check an acceptance path for a character string with respect to the nondeterministic finite automata, (Table 1 and Table 2 on pages 3, and 4);
wherein the processor is configured to generate the nondeterministic finite automata by transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction such that each node of the Glushkov automata corresponds to only one character of the regular expression pattern and the Glushkov automata has no epsilon transitions, (¶0026 regarding a pattern analyzer component incorporating a processor and memory to generate an automaton; ¶0097 regarding the pattern analyzer generating the automaton corresponding to the patterns based on common symbols between patterns; Figs. 3, and 4; ¶0029 regarding the pattern analyzer generating automaton 300 (Fig. 3), and automaton 300 being a nondeterministic finite automaton; ¶0033 regarding Fig. 4 as a nondeterministic finite automaton; Fig. 4; ¶0048 regarding a Glushkov NFA form is utilized. A Glushkov1 NFA2 is similar to a Thompson NFA construction, except a Glushkov NFA gets rid of empty (epsilon) transitions between states. A Thompson NFA construction has each node, or state, correspond to either a character from the character string or an epsilon. Since Glushkov gets rid of the epsilon transitions of Thompson, this would indicate that each node corresponds to a character);
wherein the regular expression pattern is expressed as a regular expression, (¶0013 regarding use of regular expression syntax);
wherein the processor is further configured to execute the program to perform the matching (¶0016 regarding a processor configured to execute a searching method against an automaton);
wherein the processor is further configured to execute the program to apply the matching algorithm in response to the regular expression pattern not including the extended grammar (¶0013 regarding use of regular expression syntax; ¶0025 regarding an interpreter module incorporating a processor and memory; ¶0045 regarding the interpreter module searching and matching through different paths of an automaton simultaneously);
so that all the next states that move through each character starting from a starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every state in the set of current states, and updating the set of current states to reflect new states transitioned to, (¶0025 regarding an interpreter module incorporating a processor and memory; ¶0045 regarding the interpreter module searching and matching through different paths of an automaton simultaneously3);
and when a current state includes an acceptance state at a time when all characters are consumed, it is determined that there is the acceptance path, (Table 1 and Table 2 on pages 3 and 4);
wherein the processor is further configured to execute the program to apply the matching algorithm, (¶0025 regarding an interpreter module incorporating a processor and memory; ¶0045 regarding the interpreter module searching and matching through different paths of an automaton simultaneously3);
Stewart does not explicitly teach:
or an extended regular expression
and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof,
by selecting between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not,
a first matching algorithm
However, Hron teaches:
or an extended regular expression (Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.3.2 ¶1 regarding supporting extended regular expression by including support for backreferences)
and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof, (Section 3.3.2 ¶1 regarding supporting extended regular expression by including support for backreferences; Section 3.3.2 ¶2 regarding additional support to other extensions including a look-ahead search, otherwise known as a forward search; Section 2.2.3 Definition 2.2 regarding inclusion of dereference support; Section 3.3.2 ¶1 regarding use of a capture group)
by selecting between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not, (Section 3.2 ¶1 and ¶2 regarding different methods of regular expression matching; Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.2.2 regarding a backtracking method of matching especially good for extended regular expressions that support backreferences)
a first matching algorithm (Section 3.2 ¶1 and ¶2 regarding different methods of regular expression matching; Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.2.2 regarding a backtracking method of matching especially good for extended regular expressions that support backreferences)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Stewart with the second matching algorithm of Hron because extensions, such as look-ahead, look-behind, or pattern recursion, can also be implemented when using the backtracking approach (Hron: Section 3.3.2 ¶2), furthermore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Stewart with applying a first or second matching algorithm as referenced above because one method works well for classical regular expressions (Hron: Section 3.2.3 ¶1), and because with another method, extensions, such as look-ahead, look-behind, or pattern recursion, can also be implemented when using the backtracking approach (Hron: Section 3.3.2 ¶2), furthermore it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Stewart with the extended regular expression grammar of Hron because extensions significantly increases the expressive power (Hron: Future work ¶2).
Furthermore, Stewart in view of Hron does not explicitly teach:
and wherein the matching blocks a regular expression denial of service (ReDoS) attack.
However, Tsay teaches:
and wherein the matching blocks a regular expression denial of service (ReDoS) attack. (Column 13 lines 41-44 regarding matching step of a regular expression engine designed to withstand ReDoS attacks)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Stewart in view of Hron with the teaching of Tsay to withstand regular expression denial of service (ReDoS) attacks. [Tsay: Column 13 lines 43-44].
Furthermore, Stewart does not explicitly teach:
the first matching algorithm in response to the regular expression pattern including the extended grammar,
so that a path is searched by selecting one of several next states that moves through each character starting from a starting state,
an adjacent state to the current state is separately stored along with a position on the character string,
when there is an acceptance path among paths progressed in a state selected first, matching is terminated,
and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position,
However, Hron teaches:
the first matching algorithm in response to the regular expression pattern including the extended grammar, (Section 3.3.2 ¶1 regarding supporting extended regular expression; Section 3.3 Algorithm 1 regarding a first algorithm utilizing backtracking for extended regular expressions; Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching)
so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, (Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching)
when there is an acceptance path among paths progressed in a state selected first, matching is terminated, (Section 3.4.1.1 Example 3.2 regarding an example showing the method of backtracking, and regular expression matching with an NFA until reaching the final state)
and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position, (Section 3.4.1.1 Example 3.2 regarding an example showing the method of backtracking, and regular expression matching with an NFA until reaching the final state)
Therefore, it would have been obvious before the effective filing date of the claimed invention
to one of ordinary skill in the art to which said subject matter pertains to combine Stewart with the
extended expression matching method of Hron because extensions, such as look-ahead, look-behind,
or pattern recursion, can also be implemented when using the backtracking approach (Hron: Section
3.3.2 ¶2).
Steward nor Hron does not explicitly teach:
an adjacent state to the current state is separately stored along with a position on the character string,
However, Hron does teach backtracking if a match on a current path fails, and trying another path (Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching), this would imply that the not yet searched paths, along with a position on the character string, are stored in order to backtrack to them and continue matching. Hron further teaches, storing already visited paths (Section 3.3.1 ¶2 regarding storing previously visited configurations). Separately storing an already visited path, or state, is simply an inversion of separately storing an adjacent state. Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to try storing an adjacent state along with a position on the character string instead of the previously done inverse of storing paths previously visited, as taught by Hron, because it would have been obvious to try. See MPEP 2141 (III)(E).
With regards to claim 9, Stewart in view of Hron in further view of Tsay teaches the automata processing apparatus of claim 8, as referenced above.
Stewart further teaches:
wherein the processor is further configured to execute the program to generate the nondeterministic finite automata by transforming each node to correspond to a character of the character string. (Fig. 4; ¶0048 regarding a Glushkov NFA form is utilized. A Glushkov1 NFA is similar to a Thompson NFA construction, except a Glushkov NFA gets rid of empty (epsilon) transitions2 between states. A Thompson NFA construction has each node, or state, correspond to either a character from the character string or an epsilon. Since Glushkov gets rid of the epsilon transitions of Thompson, this would indicate that each node corresponds to a character).
Prior Art Made of Record
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Regular Expression Matching Can Be Simple And Fast, Russ Cox, January 2007
This document discusses Regular expressions, as well as a few grammar extensions such as lookahead, and backreferences. This document further talks about transforming a regular expression into an NFA, as well as two different methods to search and match the regular expression in an NFA, one method being search all paths simultaneously and another method utilizing backtracking. Lastly, this document discusses potentially combining the two methods of regular expression matching. However, this document does not explicitly discuss Glushkov NFA.
K. Namjoshi and G. Narlikar, "Robust and Fast Pattern Matching for Intrusion Detection," 2010 Proceedings IEEE INFOCOM, San Diego, CA, USA, 2010, pp. 1-9, doi: 10.
This document discusses regular extended expressions and extended regular expressions. This document discusses constructing an NFA from the regular expression. Furthermore, this document discusses different methods searching and matching, including searching/matching paths simultaneously and another method of searching/matching paths utilizing backtracking. However, this document does not explicitly discuss Glushkov NFA.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JEROME ANTHONY KLOSTERMAN II whose telephone number is (571)272-0541. The examiner can normally be reached Monday - Friday 8:30am - 3:30pm ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Andrew Caldwell can be reached at 571-272-3702. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/J.A.K./Examiner, Art Unit 2182 /EMILY E LAROCQUE/ Primary Examiner, Art Unit 2182
1 Simon Fraser universityengaging the world. CourSys. (2018, November). coursys.sfu.ca/2018fa-cmpt-384-
d1/pages/GlushkovRE
Regarding Glushkov NFA construction, each symbol is an NFA state. Furthermore regarding Glushkov being epsilon
free NFAs
2 TCS -TR-A-14-73 TCS technical report fast regular expression matching. (2014, May).
alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_14_73/tcstr_14_73.pdf
Regarding Glushkov NFA not having epsilon transition
3 web.archive.org/web/20210725163813/https://www.interviewcake.com/concept/java/bfs
Regarding breadth first search algorithm
Prosecution Insights