Finite automaton construction using regular expression derivatives to simulate behavior of a backtracking engine
US11983223B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 18, 2022 |
| Grant date | May 14, 2024 |
| Priority date | — |
| Expiry date | Aug 18, 2042 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques are described herein that are capable of constructing a finite automaton using regular expression derivatives to simulate behavior of a backtracking engine. The behavior indicates an order in which paths in an input regular expression are to be evaluated by the backtracking engine. The finite automaton is constructed to include a graph that includes a root node that represents the input regular expression. Regular expressions are derived such that each derived regular expression is a regular expression derivative of the input regular expression or of another derived regular expression. Priorities are assigned to alternations in the derived regular expressions to correspond to priorities indicated by the behavior. Nodes that represent the respective derived regular expressions and transitions between respective pairs of nodes are caused to be included in the graph. Priorities, which correspond to the order, are assigned to respective branches of the graph.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.