You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Algorithmic Triviality of Abstract Structures

Article type: Research Article

Authors: Urzyczyn, Paweł

Affiliations: Warsaw University

Abstract: In the present paper we investigate algorithmically trivial structures, that is structures where every recursive function (relation) is definable by a first-order open formula. We prove that algorithmic triviality is equivalent to a property called the unwind property. We also study the notion of effective interpretation of structures and its relation to algorithmic triviality.

Keywords: algorithmic triviality, unwind property, effective interpretation, effective definitional schema

DOI: 10.3233/FI-1981-4404

Journal: Fundamenta Informaticae, vol. 4, no. 4, pp. 819-849, 1981

Received 16 January 1980
|
Published: 1 October 1981
Price: EUR 27.50
Show more