9. The system of claim 1 wherein the score of the selected partition is equal to the sum of, for each token of the array of tokens, the score specified by the dictionary data store.
1. A computerized system for transforming an input text string, the input text string being an ordered set of characters, the system comprising: a dictionary data store configured to store a plurality of tokens, wherein each token is associated with a score, and wherein each token is a string of one or more characters; a chart parser configured to generate a chart parse of the input text string, wherein: the chart parse includes a plurality of entries, each entry includes (i) an indication of a start character of the entry within the input text string and (ii) an indication of an end character of the entry within the input text string, and the chart parser is configured to, for each position within the input text string, (i) identify a string of at least one consecutive character in the input text string that begins at that position and matches one of the plurality of tokens and (ii) unless the identified string is a single character matching the start character for another entry in the chart parse, create an entry corresponding to the identified string; a partition selection module configured to determine a selected partition of the input text string based on the entries of the chart parse, wherein: the selected partition includes an array of tokens such that a concatenation of the array of tokens matches the ordered set of characters of the input text string, each of the array of tokens is selected from the chart parse, a score of the selected partition is based on a sum of, for each token of the array of tokens, the score specified by the dictionary data store, and the selected partition is a minimum score partition; a data store storing application state records; a set generation module configured to, in response to a set of tokens, select records from the data store to form a consideration set of records; and a results generation module configured to respond to the user device with a subset of the consideration set of records, wherein the subset identifies application states of applications that are relevant to a search query from the user device, wherein the input text string is based on the search query from the user device.