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 Web Ontology Language expression language profile (OWL2 EL) lacks ideas (such as negation) which can be expressed in OWL2 RL (rule language). OWL2 EL may therefore be said to have less expressive power than OWL2 RL. These restrictions allow 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 the knowledge representation language).

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:

• regardless of ease (theoretical expressivity)
• concisely and readily (practical expressivity)

The first sense dominates in areas of mathematics and logic that deal with the formal description of languages and their meaning, such as formal language theory, mathematical logic and process algebra.

In informal discussions, the term often refers to the second sense, or to both. This is often the case when discussing programming languages. Efforts have been made to formalize these informal uses of the term.

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 problems become harder to answer or completely undecidable.

Examples

Expressive power in formal language theory

Formal language theory mostly studies formalisms to describe sets of strings, such as context-free grammars and regular 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 the Chomsky hierarchy. It says, for instance, that regular expressions, nondeterministic finite automatons and regular grammars have equal expressive power, while that of context-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 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 arbitrary formal grammars, not only this problem, but every nontrivial property regarding the set of strings they describe is undecidable, a fact known as Rice'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 a <query predicate>, eg: NAME = 'Smith', in a <query statement> as "Select distinct * from

where <query sentence>;", the query engine returns the set of rows of the matching the current <query sentence> which is formed by a string (in BNF recursive syntax): "{<query sentence> := <query predicate> [<AND|OR> <query predicate>...]}". Our simple instance of query is "Select distinct * from EMPLOYEE where NAME = 'Smith';" that will give us a set of rows of the people called "Smith" (if any). The first row has a column name in each cell acting as report header. In each [[report] [cell]] (i.e. the cross of a column with a row), we have a single value whose interpretation is the corresponding header name. By the way, in our report all the cells of the column NAME will show "Smith". Now, that we know all the column names (this was the interest of the [asterisk] ('*') in our first [SQL ['select *' statement]]), if we don't like the redundant column, we can perform a "CopyPaste" (from the report to [user [source area]]) that will reuse all the column names except NAME, giving: "Select PERSONNEL_ID, FIRST_NAME, DEPT_ID, POSITION from EMPLOYEE where NAME = 'SMITH'". The expressive power of the query language starts with its capacity for managing the source of the query, ie: if the query language can perform a set expression as a [natural join] directly in the [from clause] or indirectly (several queries in a manual procedure), if the classic set operators UNION and INTERSECTION apply to sets whose members are [tuple]s of n (n>1) [degree], if there is some facility to [explode] a [[reflexive] [[associative] [entity]]] giving a reliable [bill-of-material] aka [BOM] report (for example, with the parts of the left-win of an Airbus). This facility is related with walking along the branches of a [mathematical tree] or [directed [graph]] (abbr. digraph). In this context of factories, parts and pieces EXPLODE function reports all the parts of the queried piece and (recursively) all the parts of the previous parts (until the smallest parts as a nail). The IMPLODE function is the converse of EXPLODE, ie, report all the pieces having a nail it is a walk from bottom to the relative selected top. IMPLODE easier of developping than EXPLODE is. In this area there is a big confusion about the names and the object of these niche query command. For example, in E. F. Codd terms, CLOSE, ie, [[transitive] closure] corresponds to the command EXPLODE; and OPEN (which is the Codd term for transitive reduction If the product has a practical [[query] [predicate]] for check [[<null>] [mark]]s as "<column> IS [NOT] NULL". If the DBMS product allows alternate ways to define column IS NOT NULL WITH DEFAULT. If the query language has a [report [beautifier]] able of preparing a bit the results of the GROUP clause on a data warehouse for the customary [grid [report]]s and [cubic [report]]s.

See also

• Turing tarpit
• semantic spectrum