Eingang zum Volltext in SciDok
Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291scidok39571
URL: http://scidok.sulb.unisaarland.de/volltexte/2011/3957/
On the interpretation of recursive program schemes
Quelle:  (1974) Saarbrücken, 1974  
pdfFormat: 

Institut:  Fachrichtung 6.2  Informatik  
DDCSachgruppe:  Informatik  
Dokumentart:  Report (Bericht)  
Schriftenreihe:  Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes  
Bandnummer:  1974/09  
Sprache:  Englisch  
Erstellungsjahr:  1974  
Publikationsdatum:  13.07.2011  
Kurzfassung auf Englisch:  This paper extends a previous paper [8] where we described a semantics for monadic recursive program schemes (also called Scottde Bakker schemes). The method consists in considering program schemes as rewriting systems which generate subsets of a free magma and defining a mapping of such subsets in a proper domain of functions. In our previous paper, dealing with a simple case, the combinatorial properties on which the whole construction relies were well known or at least immediate corollaries of wellknown results in the theory of contextfree languages. In the present case, the rewriting systems which we are led to consider, and which in a very naturalway could be called algebraic rewriting systems or grammars on a free magma, have been little considered in the literature and we need establish first a number of results concerning such systems. This is done in a first part of this paper. Afterwards we establish the link between such rewriting systems and recursive program schemes, define the function computed by such a scheme under a given discrete interpretation and apply the results of part I to show the equivalence of one definition of this function with the classical definitions : the operational semantics as described for example in [3], Kleene's definition of recursive function [2], the fixpoint semantics as it can be found in [5], [6] or [10].  
Lizenz:  StandardVeröffentlichungsvertrag 