# US 11,308,281 B1 · Slot type resolution process > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,281 B1 - Document ID: US11308281B1 - Status: Granted - Kind: B1 - Application number: 16/184,807 - Filed: 2018-11-08 - Granted: 2022-04-19 - Earliest claimed: 2018-11-08 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Kevin Michael Craft; Ameya Karnik; Rama Krishna Sandeep Pokkunuri - Web page: https://patentgrep.com/patent/US11308281B1 ## CPC - G06F 40/284: Lexical analysis, e.g. tokenisation or collocates - G06F 40/211: Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars - G06F 40/30: Semantic analysis - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Techniques to be used in natural language understanding (NLU) are described. For example, a NLU service to receive a request to analyze a written or spoken utterance; tokenize the received utterance; generate one or more labels corresponding to a substring of the tokenized received utterance, each of the labels including one or more slot types, by: for each path of a grammar-based finite state transducer (FST) data structure that includes instructions, traversing the path as far as possible for matches from a previous breakpoint, while maintaining i) locations of branching points and snapshots at those branching points and ii) an indication of which paths have been traversed, and recording a result of each path traversal as a generated label; resolve the one or more generated labels into machine-readable values; and output a result is described. ## Claims ### Claim 1 A computer-implemented method comprising: receiving a request to analyze text data representing a written or spoken utterance, the utterance being a user input captured by a bot; tokenizing the received text data representing the utterance; generating one or more labels corresponding to a substring of the tokenized received text data representing the utterance, each of the labels including one or more slot types, by: for each path of a grammar-based finite state transducer (FST) data structure that includes instructions, traversing the path as far as possible for matches from a previous breakpoint, while maintaining i) locations of branching points and snapshots at those branching points and ii) an indication of which paths have been traversed, wherein each of the instructions causes a performance of a defined, non-token matching action when the instruction is encountered during the traversing, and wherein one of the instructions is an instruction to call another FST; calling the another FST and traversing a path of the another FST; and recording a result of each path traversal as a generated label; resolving the one or more generated labels into machine-readable values; and outputting a result of the resolving to an entity as dictated by the request. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein maintaining the indication of which paths have been traversed comprises using one or more stacks. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein a path ends at a terminal node or a non-match. ### Claim 4 A computer-implemented method comprising: receiving a request to analyze a written or spoken utterance; tokenizing the received utterance; generating one or more labels corresponding to a substring of the tokenized received utterance, each of the labels including one or more slot types, by: for each path of a grammar-based finite state transducer (FST) data structure that includes instructions, traversing the path as far as possible for matches from a previous breakpoint, while maintaining i) locations of branching points and snapshots at those branching points and ii) an indication of which paths have been traversed, wherein each of the instructions causes a performance of a defined, non-token matching action when the instruction is encountered during the traversing, and wherein one of the instructions is an instruction to call another FST; calling the another FST and traversing a path of the another FST; and recording a result of each path traversal as a generated label; resolving the one or more generated labels into machine-readable values; and outputting a result of the resolving to an entity as dictated by the request. ### Claim 5 (depends on 4) The computer-implemented method of claim 4, wherein a path ends at a terminal node or a non-match. ### Claim 6 (depends on 4) The computer-implemented method of claim 4, further comprising: maintaining an indication of which paths have been traversed using one or more stacks. ### Claim 7 (depends on 4) The computer-implemented method of claim 4, wherein the FST references at least one slot type. ### Claim 8 (depends on 4) The computer-implemented method of claim 4, wherein the FST includes at least one instruction to cause the defined action of a match of repeating characters of a character set. ### Claim 9 (depends on 4) The computer-implemented method of claim 4, wherein the FST includes at least one instruction to cause the defined action of a match of a property defined by a grammar. ### Claim 10 (depends on 4) The computer-implemented method of claim 4, wherein the FST was generated from a grammar defining rules, slot types, and properties. ### Claim 11 (depends on 4) The computer-implemented method of claim 4, wherein the generated label is a composite label. ### Claim 12 A system comprising: a bot implemented by a first one or more electronic devices; and a natural language understanding (NLU) service implemented by a second one or more electronic devices, the NLU service including instructions that upon execution are to cause: receiving a request to analyze a written or spoken utterance; tokenizing the received utterance; generating one or more labels corresponding to a substring of the tokenized received utterance, each of the labels including one or more slot types, by: for each path of a grammar-based finite state transducer (FST) data structure that includes instructions, traversing the path as far as possible for matches from a previous breakpoint, while maintaining i) locations of branching points and snapshots at those branching points and ii) an indication of which paths have been traversed, wherein each of the instructions causes a performance of a defined, non-token matching action when the instruction is encountered during the traversing, and wherein one of the instructions is an instruction to call another FST; calling the another FST and traversing a path of the another FST; and recording a result of each path traversal as a generated label; resolving the one or more generated labels into machine-readable values; and outputting a result of the resolving to an entity as dictated by the request. ### Claim 13 (depends on 12) The system of claim 12, wherein maintaining the indication of which paths have been traversed comprises using one or more stacks. ### Claim 14 (depends on 12) The system of claim 12, wherein a path ends at a terminal node or a non-match. ### Claim 15 (depends on 12) The system of claim 12, wherein the FST references at least one slot type. ### Claim 16 (depends on 12) The system of claim 12, wherein the FST includes at least one instruction to match repeating characters of a character set. ### Claim 17 (depends on 12) The system of claim 12, wherein the FST includes at least one instruction to match a property defined by a grammar. ### Claim 18 (depends on 12) The system of claim 12, wherein the generated label is a composite label. ### Claim 19 (depends on 4) The method of claim 4, wherein the FST includes at least one instruction to cause the defined action of a call to an external function. ### Claim 20 (depends on 12) The system of claim 12, wherein the FST includes at least one instruction to cause the defined action of a call to an external function.