Zeitschriftenartikel:
S. Eberhard, S. Hetzl:
"Compressibility of Finite Languages by Grammars";
Lecture Notes in Computer Science,
9118
(2015),
S. 93
- 104.
Kurzfassung englisch:
We consider the problem of simultaneously compressing a finite set of words by a single grammar. The central result of this paper is the construction of an incompressible sequence of finite word languages. This result is then shown to transfer to tree languages and (via a previously established connection between proof theory and formal language theory) also to formal proofs in first-order predicate logic.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-19225-3_8
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.