On the complexity of the smallest grammar problem over fixed alphabets
type: Item
instance of: scholarly article
title: On the complexity of the smallest grammar problem over fixed alphabets
zbMATH Open document ID: 1464.68100
author: Katrin Casel
author: Henning Fernau
author: Serge Gaspers
author: Benjamin Gras
author: Markus L. Schmid
published in: Theory of Computing Systems
publication date: 2021-06-24T00:00:00Z
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 7363126
zbMATH Keywords: grammar-based compression
zbMATH Keywords: smallest grammar problem
zbMATH Keywords: straight-line programs
zbMATH Keywords: NP-completeness
zbMATH Keywords: exact exponential-time algorithms
describes a project that uses: TreeRePair
MaRDI profile type: Publication
full work available at URL: s00224-020-10013-w
OpenAlex ID: W3098381330
cites work: Q4386970
cites work: Q4952646
cites work: Grammar-based codes: a new class of universal lossless source codes
cites work: Universal lossless compression via multilevel pattern matching
cites work: Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
cites work: Data compression via textual substitution
cites work: Q4337021
cites work: Algorithmics on SLP-compressed strings: a survey
cites work: The Compressed Word Problem for Groups
cites work: A bisection algorithm for grammar-based compression of ordered trees
cites work: The complexity of tree automata and XPath on grammar-compressed trees
cites work: Parameter reduction and automata evaluation for grammar-compressed trees
cites work: Grammar-based compression of unranked trees
cites work: Unification with Singleton Tree Grammars
cites work: On the complexity of pattern matching for highly compressed two-dimensional texts.
cites work: Q4219050
cites work: Recompression
cites work: A lower-bound for the number of productions required for a certain class of languages
cites work: Lower bounds for context-free grammars
cites work: Concise description of finite languages
cites work: Compressibility of Finite Languages by Grammars
cites work: On minimal grammar problems for finite languages
cites work: On the grammatical complexity of finite languages
cites work: The Smallest Grammar Problem
cites work: Q4828933
cites work: Compression of individual sequences via variable-rate coding
cites work: The smallest grammar problem revisited
cites work: Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
cites work: Theory and Applications of Models of Computation
cites work: Q4198056
cites work: Independent domination in chordal graphs
cites work: Q4298260
cites work: Fundamentals of parameterized complexity
cites work: Parametrized complexity theory.
cites work: Parameterized Algorithms
cites work: Q4258216
cites work: Some simplified NP-complete graph problems
cites work: A Theorem on Coloring the Lines of a Network
cites work: \(\Delta \)-list vertex coloring in linear time
cites work: Some APX-completeness results for cubic graphs
cites work: Searching for smallest grammars on large sequences and application to DNA
cites work: Q5181716
cites work: Q5550921
cites work: On the algorithmic complexity of twelve covering and independence parameters of graphs
cites work: Extremal Values of the Interval Number of a Graph
cites work: Q4368728
cites work: Fast algorithms for min independent dominating set
cites work: Q4027320
cites work: Efficient Generation of Minimal Length Addition Chains
DOI: 10.1007/S00224-020-10013-W
description: scientific article; zbMATH DE number 7363126