While current Semantic Web languages and technologies are well-suited for accessing and integrating static data, methods and technologies for the handling of dynamic aspects – required in many modern web environments – are largely missing. We propose to use Abstract State Machines (ASMs) as the formal basis for dealing with changes in Linked Data, which is the combination of the Resource Description Framework (RDF) with the Hypertext Transfer Protocol (HTTP). We provide a synthesis of ASMs and Linked Data and show how the combination aligns with the relevant specifications such as the Request/Response communication in HTTP, the guidelines for updating resource state in the Linked Data Platform (LDP) specification, and the formal grounding of RDF in model theory. Based on the formalisation of Linked Data resources that change state over time, we present the syntax and operational semantics of a small rule-based language to specify user agents that use HTTP to interact with Linked Data as the interface to the environment. We show the feasibility of the approach in an evaluation involving the specification of automation in a Smart Building scenario, where the presented approach serves as a theoretical foundation.