A behavioural theory for reflective sequential algorithms

Autoren Klaus-Dieter Schewe
Flavio Ferrarotti
Loredana Tec
Editoren Alexander K. Petrenko
Andrei Voronkov
Titel A behavioural theory for reflective sequential algorithms
Buchtitel Perspectives of Systems Informatics - PSI 2017, Revised Selected Papers
Typ in Konferenzband
Verlag Springer
Serie Lecture Notes in Computer Science
Band 10742
ISBN 978-3-319-74312-7
DOI 10.1007/978-3-319-74313-4_10
Monat January
Jahr 2018
Seiten 117-131
SCCH ID# 16091

We develop a behavioural theory of reective sequential algorithms (RSAs), i.e. algorithms that can modify their own behaviour. The theory comprises a set of language-independent postulates characterising the class of RSAs, an abstract machine model that provably satisfies the postulates, and a proof that all RSAs are captured by this machine model. As in Gurevich's thesis for sequential algorithms RSAs are sequential-time, bounded parallel algorithms, where the bound depends on the algorithm only and not on the input. Different from the class of sequential algorithms every state of an RSA includes a representation of the algorithm in that state, thus enabling linguistic reection. The model of reective Abstract State Machines (rASMs) extends sequential ASMs using extended states that include an updatable representation of the main ASM rule to be executed by the machine in that state.