Incomputer science, theexpressive power (also calledexpressiveness orexpressivity) of alanguage is the breadth ofideas 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, theWeb Ontology Language expression language profile (OWL2 EL) lacks ideas (such asnegation) that can be expressed in OWL2 RL (rule language). OWL2 EL may therefore be said to have lessexpressive power than OWL2 RL. These restrictions allow for more efficient (polynomial time) reasoning in OWL2 EL than in OWL2 RL. So OWL2 EL trades some expressive power for more efficient reasoning (processing of theknowledge representation language).[1]
The termexpressive power may be used with a range of meaning. It may mean a measure of the ideas expressible in that language:[2]
The first sense dominates in areas ofmathematics andlogic that deal with the formal description of languages and their meaning, such asformal language theory,mathematical logic andprocess algebra.[2]
In informal discussions, the term often refers to the second sense, or to both. This is often the case when discussingprogramming 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 completelyundecidable.[5]
 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Expressive power" computer science – news ·newspapers ·books ·scholar ·JSTOR(April 2010) (Learn how and when to remove this message) |
Formal language theory mostly studies formalisms to describe sets ofstrings, such ascontext-free grammars andregular expressions. Each instance of a formalism, e.g. each grammar and each regular expression, describes a particular set of strings. In this context, the expressive power of a formalism is the set of sets of strings its instances describe, and comparing expressive power is a matter of comparing these sets.
An important yardstick for describing the relative expressive power of formalisms in this area is theChomsky hierarchy. It says, for instance, thatregular expressions,nondeterministic finite automata andregular grammars have equal expressive power, while that ofcontext-free grammars is greater; what this means is that the sets of sets of strings described by the first three formalisms are equal, and a proper subset of the set of sets of strings described by context-free grammars.
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 iscompletely 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 aTuring complete formalism, such as arbitraryformal grammars, not only this problem, butevery nontrivial property regarding the set of strings they describe is undecidable, a fact known asRice's Theorem.
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. inO(1)), while the reverse is not possible.
Similar considerations apply to formalisms that describe not sets of strings, but sets oftrees (e.g.XML schema languages), ofgraphs, or other structures.
Database theory is concerned, among other things, withdatabase queries, e.g.formulas that, given the contents of a database, specify certain information to be extracted from it. In the predominantrelational database paradigm, the contents of a database are described as a finite set of finitary mathematical relations; Boolean queries, that always yieldtrue orfalse, are formulated infirst-order logic.
It turns out thatfirst-order logic is lacking in expressive power: it cannot express certain types of Boolean queries, e.g. queries involvingtransitive 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., forsecond-order logic. Consequently, a literature sprang up in which manyquery languages and language constructs were compared on the basis of expressive power and efficiency, e.g. various versions ofDatalog.[7]
Similar considerations apply for query languages on other types of data, e.g. XML query languages such asXQuery.
