In my article Uninstall AppV 5.0 package automatically if a user is removed from a user based collection in SCCM 2012 I described how an application is removed if an user is removed from an user based collection.
In this article I will describe how an application is uninstalled if a computer is removed from a device based collection.

Create the computer based uninstall query

On page 30 in the document Managing AppV5 with Configuration Manager 2012SP1 (this document has been removed) it is described how a computer based uninstall collection is made.

The query is:

SELECT SMS_R_SYSTEM.ResourceID,SMS_R_SYSTEM.ResourceType,SMS_R_SYSTEM.Name,SMS_R_SYSTEM.SMSUniqueIdentifier,SMS_R_SYSTEM.ResourceDomainORWorkgroup,SMS_R_SYSTEM.Client
FROM
SMS_R_System INNER JOIN SMS_G_System_AppClientState ON SMS_G_System_AppClientState.MachineName = SMS_R_System.Name
WHERE 
SMS_G_System_AppClientState.ComplianceState = "1"
AND 
SMS_G_System_AppClientState.AppName ="Mozilla_Firefox_24_DUT_WIN7"

Create the uninstall deployment

The application ‘Mozilla_Firefox_24_DUT_WIN7’ has both an install and uninstall deployment.