Examples of CF-bi-inmune and CF-levelable sets in LOGSPACE

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/110922

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor	Facultat d'Informàtica de Barcelona
dc.contributor	Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Balcázar Navarro, José Luis
dc.contributor.author	Díaz Cort, Josep
dc.contributor.author	Gabarró Vallès, Joaquim
dc.date	1984
dc.identifier.citation	Balcazar, J. L., Diaz, J., Gabarro, J. "Examples of CF-bi-inmune and CF-levelable sets in LOGSPACE". 1984.
dc.identifier.uri	http://hdl.handle.net/2117/110922
dc.language.iso	eng
dc.relation	84/08
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Llenguatges de programació
dc.subject	Computational complexity
dc.subject	LOGSPÂCE
dc.subject	CF-bi-inmune language
dc.subject	CF-levelable language
dc.subject	Complexitat computacional
dc.title	Examples of CF-bi-inmune and CF-levelable sets in LOGSPACE
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.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.
dc.description.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ó

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Uniform characterizations of non-uniform complexity measures

Balcázar Navarro, José Luis; Díaz Cort, Josep; Gabarró Vallès, Joaquim

On some "non uniform" complexity measures

Balcázar Navarro, José Luis; Díaz Cort, Josep; Gabarró Vallès, Joaquim

Algorithms for learning finite automata from queries: a unified view

Balcázar Navarro, José Luis; Díaz Cort, Josep; Gavaldà Mestre, Ricard; Watanabe, Osamu

Nonuniform complexity classes specified by lower and upper bounds

Balcázar Navarro, José Luis; Gabarró Vallès, Joaquim

Connections among non uniform models for problems requiring high amount of resources

Balcázar Navarro, José Luis; Gabarró Vallès, Joaquim

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio