Publications in Scientific Journals:
S. Eberhard, S. Hetzl:
"Compressibility of Finite Languages by Grammars";
Lecture Notes in Computer Science,
9118
(2015),
93
- 104.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-19225-3_8
Created from the Publication Database of the Vienna University of Technology.