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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Balcázar Navarro, José Luis
dc.contributor.author	Gavaldà Mestre, Ricard
dc.contributor.author	Watanabe, Osamu
dc.date	1996-09
dc.identifier.citation	Balcazar, J. L., Gavaldà, R., Watanabe, O. "Coding complexity: the computational complexity of succinct descriptions". 1996.
dc.identifier.uri	http://hdl.handle.net/2117/83108
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	Complexity
dc.subject	Sets of strings
dc.subject	Descriptions
dc.title	Coding complexity: the computational complexity of succinct descriptions
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.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.