2013/07/06 by Florian Benz, Timo Kötzing · 2 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #Natural Language Processing Techniques #DNA and Biological Computing
paper · doi:10.1145/2463372.2463441
openalex publication_date 2013/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The smallest grammar problem is the problem of finding the smallest context-free grammar that generates exactly one given sequence. Approximating the problem with a ratio of less than 8569/8568 is known to be NP-hard. Most work on this problem has focused on finding decent solutions fast (mostly in linear time), rather than on good heuristic algorithms. Inspired by a new perspective on the problem presented by Carrascosa et al. (2010), we investigate the performance of different heuristics on the problem. The aim is to find a good solution on large instances by allowing more than linear time. We propose a hybrid of a max-min ant system and a genetic algorithm that in combination with a novel local search outperforms the state of the art on all files of the Canterbury corpus, a standard benchmark suite. Furthermore, this hybrid performs well on a standard DNA corpus.