Quantitative Generalizations of Languages


Thomas A. Henzinger

A language is a set of words, i.e., a function from words to booleans. There are two different quantitative generalizations of languages. A probabilistic language is a set of probability spaces on words. A numerical language is a function from words to reals, where the value of a word represents a cost. We review some classical problems about languages in these two quantitative settings.

Proceedings of the 11th International Conference on Developments in Language Theory (DLT), Lecture Notes in Computer Science 4588, Springer, 2007, pp. 20-22.


Download inofficial, sometimes updated PostScript / PDF document. © 2007 Springer.