On the complexity of the smallest grammar problem over fixed alphabets

DOI10.1007/S00224-020-10013-WMaRDI QIDQ2035481zbMATHOpenAlexFDO

Authors Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid

Publication date 24 June 2021

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-020-10013-w

zbMATH Keywords

NP-completenessgrammar-based compressionstraight-line programssmallest grammar problemexact exponential-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Recommendations

• On the complexity of grammar-based compression over fixed alphabets
• The Smallest Grammar Problem
• The smallest grammar problem as constituents choice and minimal grammar parsing
• Choosing word occurrences for the smallest grammar problem
• The smallest grammar problem revisited

Cites work

• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1149447 (Why is no real title available?)
• scientific article; zbMATH DE number 2119662 (Why is no real title available?)
• scientific article; zbMATH DE number 1445329 (Why is no real title available?)
• scientific article; zbMATH DE number 3428958 (Why is no real title available?)
• scientific article; zbMATH DE number 3266380 (Why is no real title available?)
• A Theorem on Coloring the Lines of a Network
• A bisection algorithm for grammar-based compression of ordered trees
• A lower-bound for the number of productions required for a certain class of languages
• Algorithmics on SLP-compressed strings: a survey
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Compressibility of Finite Languages by Grammars
• Compression of individual sequences via variable-rate coding
• Concise description of finite languages
• Data compression via textual substitution
• Efficient Generation of Minimal Length Addition Chains
• Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
• Extremal Values of the Interval Number of a Graph
• Fast algorithms for min independent dominating set
• Fundamentals of parameterized complexity
• Grammar-based codes: a new class of universal lossless source codes
• Independent domination in chordal graphs
• Lower bounds for context-free grammars
• On minimal grammar problems for finite languages
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• On the complexity of pattern matching for highly compressed two-dimensional texts.
• On the grammatical complexity of finite languages
• Parameter reduction and automata evaluation for grammar-compressed trees
• Parameterized algorithms
• Parametrized complexity theory.
• Recompression: a simple and powerful technique for word equations
• Searching for smallest grammars on large sequences and application to DNA
• Some APX-completeness results for cubic graphs
• Some simplified NP-complete graph problems
• The Compressed Word Problem for Groups
• The Smallest Grammar Problem
• The complexity of tree automata and XPath on grammar-compressed trees
• The smallest grammar problem revisited
• Theory and Applications of Models of Computation
• Unification with Singleton Tree Grammars
• Universal lossless compression via multilevel pattern matching
• \(\Delta \)-list vertex coloring in linear time

Cited in

(7)

• Pareto grammars
• Choosing word occurrences for the smallest grammar problem
• Searching for smallest grammars on large sequences and application to DNA
• On minimal grammar problems for finite languages
• On the complexity of grammar-based compression over fixed alphabets
• Finding the smallest binarization of a CFG is NP-hard
• The smallest grammar problem as constituents choice and minimal grammar parsing

Describes a project that uses

Uses Software

• TreeRePair

This page was built for publication: On the complexity of the smallest grammar problem over fixed alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035481)