On the Succinctness of Different Representations of Languages
Juris Hartmanis · SIAM Journal on Computing · 1980
The purposes of this paper is to give simple new proofs of some interesting recent results about the relative succinctness of different representations of regular, deterministic and unambiguous context-free languages and to derive some new results about how the relative succinctness of representations change when the representations contain a formal proof that the languages generated are in the desired subclass of languages.