On the compressibility of finite languages and formal proofs
type: Item
instance of: scholarly article
title: On the compressibility of finite languages and formal proofs
zbMATH Open document ID: 1390.68389
author: Sebastian Eberhard
author: Stefan Hetzl
published in: Information and Computation
publication date: 2018-03-21T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 6851687
Wikidata QID: Q113872847
MaRDI profile type: Publication
full work available at URL: j.ic.2017.09.001
OpenAlex ID: W2751273904
cites work: The macro model for data compression (Extended Abstract)
cites work: On the Complexity of Grammar-Based Compression over Fixed Alphabets
cites work: Q4386970
cites work: Grammar-based codes: a new class of universal lossless source codes
cites work: Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
cites work: The Smallest Grammar Problem
cites work: A fully linear-time approximation algorithm for grammar-based compression
cites work: Approximation of grammar-based compression via recompression
cites work: A \textit{really} simple approximation of smallest grammar
cites work: Algorithmics on SLP-compressed strings: a survey
cites work: Concise description of finite languages
cites work: A note on a problem in the theory of grammatical complexity
cites work: A lower-bound for the number of productions required for a certain class of languages
cites work: Context-free complexity of finite languages
cites work: On the context-free production complexity of finite languages
cites work: Applying Tree Languages in Proof Theory
cites work: Towards Algorithmic Cut-Introduction
cites work: Algorithmic introduction of quantified cuts
cites work: Introducing Quantified Cuts in Logic with Equality
cites work: Minimal cover-automata for finite languages
cites work: Twelve Problems in Proof Complexity
cites work: Compressibility of Finite Languages by Grammars
cites work: Q3862379
cites work: Rigid tree automata and applications
cites work: Proof theory. 2nd ed
cites work: Q3618853
cites work: Untersuchungen über das logische Schliessen. II
cites work: The number of proof lines and the size of proofs in first order logic
cites work: Lower Bounds on Herbrand's Theorem
cites work: Q3866101
cites work: Q4215637
cites work: The epsilon calculus and Herbrand complexity
cites work: Complexity of resolution proofs and function introduction
cites work: Q4304753
cites work: Q4263791
cites work: Automated Reasoning
cites work: On the form of witness terms
cites work: Herbrand Disjunctions, Cut Elimination and Context-Free Tree Grammars
cites work: Herbrand Confluence for First-Order Proofs with Π2-Cuts
DOI: 10.1016/J.IC.2017.09.001
description: scientific article; zbMATH DE number 6851687