A behavioural theory for reflective sequential algorithms

DOI10.1007/978-3-319-74313-4_10zbMATH Open1461.68083arXiv2001.01873OpenAlexW2784334896MaRDI QIDQ4989672FDOQ4989672

Authors: Flavio Ferrarotti, Klaus-Dieter Schewe, Loredana Tec

Publication date: 26 May 2021

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We develop a behavioural theory of reflective sequential algorithms (RSAs), i.e. sequential algorithms that can modify their own behaviour. The theory comprises a set of language-independent postulates defining the class of RSAs, an abstract machine model, and the proof that all RSAs are captured by this machine model. As in Gurevich's behavioural theory 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 reflection. Bounded exploration is preserved using terms as values. The model of reflective sequential abstract state machines (rsASMs) 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. Updates to the representation of ASM signatures and rules are realised by means of a sophisticated tree algebra.

Full work available at URL: https://arxiv.org/abs/2001.01873

Recommendations

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) General topics in the theory of algorithms (68W01) Classical models of computation (Turing machines, etc.) (68Q04)

Cited In (6)

This page was built for publication: A behavioural theory for reflective sequential algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989672)