Expressive power (computer science)
In computer science, the expressive power (also called expressiveness or expressivity) of a language is the breadth of ideas that can be represented and communicated in that language. The more expressive a language is, the greater the variety and quantity of ideas it can be used to represent.
For example, the
Information description
The term expressive power may be used with a range of meaning. It may mean a measure of the ideas expressible in that language:[2]
- regardless of ease (theoretical expressivity)
- concisely and readily (practical expressivity)
The first sense dominates in areas of
In informal discussions, the term often refers to the second sense, or to both. This is often the case when discussing programming languages.[3][page needed] Efforts have been made to formalize these informal uses of the term.[4]
The notion of expressive power is always relative to a particular kind of thing that the language in question can describe, and the term is normally used when comparing languages that describe the same kind of things, or at least comparable kinds of things.[4]
The design of languages and formalisms involves a trade-off between expressive power and analyzability. The more a formalism can express, the harder it becomes to understand what instances of the formalism say. Decision problems become harder to answer or completely undecidable.[5]
Examples
In formal language theory
This article needs additional citations for verification. (April 2010) |
An important yardstick for describing the relative expressive power of formalisms in this area is the
In this area, the cost of expressive power is a central topic of study. It is known, for instance, that deciding whether two arbitrary regular expressions describe the same set of strings is hard, while doing the same for arbitrary context-free grammars is completely impossible. However, it can still be efficiently decided whether any given string is in the set.
For more expressive formalisms, this problem can be harder, or even undecidable. For a
There are some results on conciseness as well; for instance, nondeterministic finite automata and regular grammars are more concise than regular expressions, in the sense that the latter can be translated to the former without a blowup in size (i.e. in
Similar considerations apply to formalisms that describe not sets of strings, but sets of
In database theory
It turns out that first-order logic is lacking in expressive power: it cannot express certain types of Boolean queries, e.g. queries involving transitive closure.[6] However, adding expressive power must be done with care: it must still remain possible to evaluate queries with reasonable efficiency, which is not the case, e.g., for second-order logic. Consequently, a literature sprang up in which many query languages and language constructs were compared on the basis of expressive power and efficiency, e.g. various versions of Datalog.[7]
Similar considerations apply for query languages on other types of data, e.g. XML query languages such as XQuery.
See also
References
- ^
ISSN 1570-8268.
- ^ a b
Farmer, William (2007). "Chiron: A multi-paradigm logic". In R. Matuszewski; A. Zalewska (eds.). From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Studies in Logic, Grammar and Rhetoric. pp. 1–19. ISBN 978-83-7431-128-1.
- Abelson and Sussman
- ^ .
- .
- ^ Serge Abiteboul, Richard B. Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.
- ^ Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov: Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3): 374-425 (2001).