Coding complexity: the computational complexity of succinct descriptions

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/83108

Title:	Coding complexity: the computational complexity of succinct descriptions
Author:	Balcázar Navarro, José Luis; Gavaldà Mestre, Ricard; Watanabe, Osamu
Other authors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Abstract:	For a given set of strings, the problem of obtaining a succinct description becomes an important subject of research, related to several areas of theoretical computer science. In structural complexity theory, researchers have developed a reasonable framework for studying the complexity of these problems. In this paper, we survey how such investigation has proceeded, and explain the current status of our knowledge.
Subject(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Complexity -Sets of strings -Descriptions
Rights:
Document type:	Article - Published version Report
Share: