Mostrar el registro sencillo del ítem
dc.contributor.author
Carrascosa, Rafael
dc.contributor.author
Coste, François
dc.contributor.author
Galle, Matthias
dc.contributor.author
Infante Lopez, Gabriel Gaston
dc.date.available
2023-04-13T10:26:22Z
dc.date.issued
2011-10
dc.identifier.citation
Carrascosa, Rafael; Coste, François; Galle, Matthias; Infante Lopez, Gabriel Gaston; The Smallest Grammar Problem as Constituents Choice and Minimal Grammar Parsing; MDPI; Algorithms; 4; 4; 10-2011; 262-284
dc.identifier.issn
1999-4893
dc.identifier.uri
http://hdl.handle.net/11336/193597
dc.description.abstract
The smallest grammar problem—namely, finding a smallest context-free grammar that generates exactly one sequence—is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and pattern discovery. We propose a new perspective on this problem by splitting it into two tasks: (1) choosing which words will be the constituents of the grammar and (2) searching for the smallest grammar given this set of constituents. We show how to solve the second task in polynomial time parsing longer constituent with smaller ones. We propose new algorithms based on classical practical algorithms that use this optimization to find small grammars. Our algorithms consistently find smaller grammars on a classical benchmark reducing the size in 10% in some cases. Moreover, our formulation allows us to define interesting bounds on the number of small grammars and to empirically compare different grammars of small size.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
MDPI
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
DATA DISCOVERY
dc.subject
HIERARCHICAL STRUCTURE INFERENCE
dc.subject
OPTIMAL PARSING
dc.subject
SMALLEST GRAMMAR PROBLEM
dc.subject.classification
Otras Ciencias de la Computación e Información
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
The Smallest Grammar Problem as Constituents Choice and Minimal Grammar Parsing
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2023-04-11T14:30:30Z
dc.journal.volume
4
dc.journal.number
4
dc.journal.pagination
262-284
dc.journal.pais
Estados Unidos
dc.description.fil
Fil: Carrascosa, Rafael. Universidad Nacional de Córdoba; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Córdoba; Argentina
dc.description.fil
Fil: Coste, François. Institut National de Recherche en Informatique et en Automatique; Francia
dc.description.fil
Fil: Galle, Matthias. Institut National de Recherche en Informatique et en Automatique; Francia
dc.description.fil
Fil: Infante Lopez, Gabriel Gaston. Universidad Nacional de Córdoba; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Córdoba; Argentina
dc.journal.title
Algorithms
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://www.mdpi.com/1999-4893/4/4/262/
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.3390/a4040262
Archivos asociados