- Expressive power
In

computer science , the**expressive power**of a language may refer to:

* what can be said in the language (at all)

* how concisely it can be said.In informal discussions, the term often refers to the latter sense, or both; e.g. this is often the case when discussing

programming language s, e.g. in [*"*] . Efforts have been made to formalize these informal uses of the term, e.g. [Structure and Interpretation of Computer Programs ", by Abelson and Sussman*[*] .*http://citeseer.ist.psu.edu/felleisen90expressive.html "On the Expressive Power of Programming Languages", by Matthias Felleisen (1990)*]Formal discussions mostly use the term in its former sense, using "conciseness" for the latter sense. This is the case in areas of

mathematics that deal with the exact description of languages and their meaning, such asformal language theory ,mathematical logic andprocess algebra .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.

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 problem s become harder to answer or completelyundecidable .**Examples****Expressive power in formal language theory**Formal language theory mostly studies formalisms to describe sets of strings, such ascontext-free grammar s andregular expression s. 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 the

Chomsky hierarchy . It says, for instance, thatregular expression s,nondeterministic state machine s andregular grammar s have equal expressive power, while that ofcontext-free grammar s 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 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

Turing complete formalism, such as arbitraryformal grammar s, not only this problem, but "every" 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 state machines 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

O(1) ), while the reverse is not possible.Similar considerations apply to formalisms that describe not sets of strings, but sets of trees (e.g. XML schema languages), of graphs, or other structures.

**Expressive power in database theory**Database theory is concerned, among other things, with database queries, e.g. formulas that given the contents of a database extract certain information from it. In the predominantrelational database paradigm, the contents of a database are described as a finite set of finite mathematical relations; Boolean queries, that always yield "true" or "false", are formulated infirst-order logic .It turns out that

first-order logic is lacking in expressive power: it cannot express certain types of Boolean queries, e.g. queries involvingtransitive closure [] . 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., forSerge Abiteboul ,Richard B. Hull ,Victor Vianu : Foundations of Databases. Addison-Wesley, 1995.second-order logic . Consequently, a literature sprang up in which manyquery language s and language constructs were compared on expressive power and efficiency, e.g. various versions ofDatalog [] .Evgeny Dantsin ,Thomas Eiter ,Georg Gottlob , andAndrei Voronkov : Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3): 374-425 (2001).Similar considerations apply for query languages on other types of data, e.g. XML query languages such as

XQuery .**References****See also***

Turing tarpit

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**expressive**— expressive, eloquent, significant, meaningful, pregnant, sententious mean clearly conveying or manifesting a thought, idea, or feeling or a combination of these. Something is expressive which vividly or strikingly represents the thoughts,… … New Dictionary of Synonyms**Power of Beat**— était un groupe musical underground emblématique des années 90. Le groupe Il était composé de Tim stuart, Romy butter et Susan virgin. Après la vague Acid jazz qui a déferlé sur la France et la Belgique, le groupe se réclame de la post new beat.… … Wikipédia en Français**power**— by Claire Colebrook Although the concept of power in French philosophy is usually associated with Michel Foucault, and although Deleuze and Guattari in A Thousand Plateaus are explicitly critical of Foucault s use of the word power (rather… … The Deleuze dictionary**power**— by Claire Colebrook Although the concept of power in French philosophy is usually associated with Michel Foucault, and although Deleuze and Guattari in A Thousand Plateaus are explicitly critical of Foucault s use of the word power (rather… … The Deleuze dictionary**expressive**— expressively, adv. expressiveness, n. /ik spres iv/, adj. 1. full of expression; meaningful: an expressive shrug. 2. serving to express; indicative of power to express: a look expressive of gratitude. 3. of, pertaining to, or concerned with… … Universalium**expressive**— /əkˈsprɛsɪv / (say uhk spresiv), /ɛk / (say ek ) adjective 1. serving to express; indicative of power to express: a look expressive of gratitude. 2. full of expression, as the face or voice. 3. of, relating to, or concerned with expression.… … Australian English dictionary**Equal power relationship**— Peacemaking and feminist theory coined the term equal power relationship to describe a situation in which neither partner had a clear power over the other. It has since come into more general use.Perception and reinforcement of an equal power… … Wikipedia**arts, East Asian**— Introduction music and visual and performing arts of China, Korea, and Japan. The literatures of these countries are covered in the articles Chinese literature, Korean literature, and Japanese literature. Some studies of East Asia… … Universalium**painting, Western**— ▪ art Introduction history of Western painting from its beginnings in prehistoric times to the present. Painting, the execution of forms and shapes on a surface by means of pigment (but see also drawing for discussion of depictions in … Universalium**dance**— dancingly, adv. /dans, dahns/, v., danced, dancing, n. v.i. 1. to move one s feet or body, or both, rhythmically in a pattern of steps, esp. to the accompaniment of music. 2. to leap, skip, etc., as from excitement or emotion; move nimbly or… … Universalium