Limiting characterizations of low level space complexity classes
Michèle Angelaccio, Marco Protasi · RAIRO - Theoretical Informatics and Applications · 1993
The concept of limiting approximation, initially introduced for recursive functions, has been applied in [AP9Ö] and in [APA91] in the framework of the computaüonal complexity theory to détermine meaningful characterizations of well known complexity classes.This investigation allowed to characterize PSP ACE and other higher space complexity classes.In this paper we continue this study, considering space classes of lower complexity not studied yet from this point ofview.In particular we characterize LOG SPACE and LIN SPACE. Résumé. -Le concept d'approximation à la limite, introduit initialement pour les fonctions récursives, a été appliqué dans [AP90] et [APA91]dans le cadre de la théorie de la complexité pour définir des caractérisations significatives de classes de complexité.Cette étude permet de caractériser PSP ACE et d'autres classes de complexité de niveau supérieur.Dans cet article, nous poursuivons cette étude en considérant des classes de complexité de plus bas niveau qui n'ont pas encore été étudiées de ce point de vue.En particulier nous caractérisons LOGSPACE et LIN SPACE.