In the traditional view, a language is a set of words, i.e., a function from words to boolean values. We call this view “qualitative,” because each word either belongs to or does not belong to a language. Let Σ be an alphabet, and let us consider infinite words over Σ. Formally, a qualitative language over Σ is a function A: B . There are many applications of qualitative languages. For example, qualitative languages are used to specify the legal behaviors of systems, and zero-sum objectives of games played on graphs. In the former case, each behavior of a system is either legal or illegal; in the latter case, each outcome of a game is either winning or losing. For defining languages, it is convenient to use finite acceptors (or generators). In particular, qualitative languages are often defined using finite-state machines (so-called ω-automata) whose transitions are labeled by letters from Σ. For example, the states of an ω-automaton may represent states of a system, and the transition labels may represent atomic observables of a behavior. There is a rich and well-studied theory of finite-state acceptors of qualitative languages, namely, the theory of theω-regular languages.
This research was supported in part by the Swiss National Science Foundation and by the NSF grant CCR-0225610.
20 - 22
DLT: Developments in Language Theory
Henzinger TA. Quantitative generalizations of languages. In: Vol 4588. Springer; 2007:20-22. doi:10.1007/978-3-540-73208-2_2
Henzinger, T. A. (2007). Quantitative generalizations of languages (Vol. 4588, pp. 20–22). Presented at the DLT: Developments in Language Theory, Springer. https://doi.org/10.1007/978-3-540-73208-2_2
Henzinger, Thomas A. “Quantitative Generalizations of Languages,” 4588:20–22. Springer, 2007. https://doi.org/10.1007/978-3-540-73208-2_2.
T. A. Henzinger, “Quantitative generalizations of languages,” presented at the DLT: Developments in Language Theory, 2007, vol. 4588, pp. 20–22.
Henzinger TA. 2007. Quantitative generalizations of languages. DLT: Developments in Language Theory, LNCS, vol. 4588, 20–22.
Henzinger, Thomas A. Quantitative Generalizations of Languages. Vol. 4588, Springer, 2007, pp. 20–22, doi:10.1007/978-3-540-73208-2_2.