Relationally defined clones of tree functions closed under selection or primitive recursion

We investigate classes of tree functions which are closed under composition and primitive recursion or selection (a restricted form of recursion). The main result is the characterization of those finitary relations ς (on the set of all trees of a fixed signature) for which the clone of tree function...

Full description

Saved in:
Bibliographic Details
Main Authors: Pöschel Reinhard
Semigrodskij Aleksander
Vogler Heiko
Format: Article
Published: 2004
Series:Acta cybernetica 16 No. 3
Kulcsszavak:Számítástechnika, Nyelvészet - számítógép alkalmazása
Subjects:
Online Access:http://acta.bibl.u-szeged.hu/12731
Description
Summary:We investigate classes of tree functions which are closed under composition and primitive recursion or selection (a restricted form of recursion). The main result is the characterization of those finitary relations ς (on the set of all trees of a fixed signature) for which the clone of tree functions preserving ς is closed under selection. Moreover, it turns out that such clones are closed also under primitive recursion.
Physical Description:411-425
ISSN:0324-721X