A method includes receiving a search query from a user device and identifying function records using the search query. Each function record includes an application access mechanism (AAM) and application state information (ASI). The AAM includes a reference to a native application and indicates one or more operations for the application to perform. The ASI describes a state of the application after the application has performed the operations. Identifying the function records may be based on matches between terms of the search query and terms of the ASI included in the function records. The techniques further include selecting AAMs from the identified function records and identifying one or more AAMs of the selected AAMs that are compatible with the user device. The techniques also include transmitting the identified AAMs to the user device and refraining from transmitting any of the selected AAMs that are not compatible with the user device.