Title:
|
Examples of CF-bi-inmune and CF-levelable sets in LOGSPACE
|
Author:
|
Balcázar Navarro, José Luis; Díaz Cort, Josep; Gabarró Vallès, Joaquim
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Facultat d'Informàtica de Barcelona; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
Abstract:
|
We find sets in the class LOGSPACE (on-line) that do not have good respectively approximations by context-free languages. For that we introduce the languages CF-bi-inmune and CF-levelable. We prove the results by defining directectly the sets and obtaining the properties via pumping arguments. |
Abstract:
|
Trobem conjunts en la classe LOGSPACE (on-line) que no tenen bones respectivament òptimes aproximacions per llenguatges incontextuals. Per això introduïm els llenguatges CF-bi-inmune i CF-nivellable. Demostrem els resultats directament, definim els llenguatges i demostrem les propietats mitjançant el lema d'iteracció |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Llenguatges de programació -Computational complexity -LOGSPÂCE -CF-bi-inmune language -CF-levelable language -Complexitat computacional |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|