En informática , el poder expresivo (también llamado expresividad o expresividad ) de un lenguaje es la amplitud de ideas que se pueden representar y comunicar en ese lenguaje. Cuanto más expresivo sea un lenguaje, mayor será la variedad y cantidad de ideas que puede utilizar para representar.
Por ejemplo, el perfil de lenguaje de expresión del lenguaje de ontología web (OWL2 EL) carece de ideas (como la negación ) que se pueden expresar en OWL2 RL (lenguaje de reglas). Por lo tanto, se puede decir que OWL2 EL tiene menos poder expresivo que OWL2 RL. Estas restricciones permiten un razonamiento más eficiente ( tiempo polinomial ) en OWL2 EL que en OWL2 RL. Por lo tanto, OWL2 EL intercambia algo de poder expresivo por un razonamiento más eficiente (procesamiento del lenguaje de representación del conocimiento ). [1]
El término poder expresivo puede utilizarse con diversos significados. Puede significar una medida de las ideas expresables en ese idioma: [2]
El primer sentido domina en áreas de las matemáticas y la lógica que tratan de la descripción formal de los lenguajes y su significado, como la teoría del lenguaje formal , la lógica matemática y el álgebra de procesos . [2]
En las discusiones informales, el término suele referirse al segundo sentido, o a ambos. Este suele ser el caso cuando se habla de lenguajes de programación . [3] [ página necesaria ] Se han hecho esfuerzos para formalizar estos usos informales del término. [4]
La noción de poder expresivo siempre es relativa a un tipo particular de cosa que el lenguaje en cuestión puede describir, y el término normalmente se utiliza cuando se comparan lenguajes que describen el mismo tipo de cosas, o al menos tipos de cosas comparables. [4]
El diseño de lenguajes y formalismos implica un equilibrio entre poder expresivo y analizabilidad. Cuanto más puede expresar un formalismo, más difícil resulta entender lo que dicen las instancias del formalismo. Los problemas de decisión se vuelven más difíciles de responder o completamente indecidibles . [5]
La teoría del lenguaje formal estudia principalmente los formalismos para describir conjuntos de cadenas , como las gramáticas independientes del contexto y las expresiones regulares . Cada instancia de un formalismo, por ejemplo, cada gramática y cada expresión regular, describe un conjunto particular de cadenas. En este contexto, el poder expresivo de un formalismo es el conjunto de conjuntos de cadenas que describen sus instancias, y comparar el poder expresivo es una cuestión de comparar estos conjuntos.
Un criterio importante para describir el poder expresivo relativo de los formalismos en esta área es la jerarquía de Chomsky . Esta dice, por ejemplo, que las expresiones regulares , los autómatas finitos no deterministas y las gramáticas regulares tienen el mismo poder expresivo, mientras que el de las gramáticas libres de contexto es mayor; lo que esto significa es que los conjuntos de conjuntos de cadenas descritos por los tres primeros formalismos son iguales, y un subconjunto propio del conjunto de conjuntos de cadenas descritos por gramáticas libres de contexto.
En esta área, el costo del poder expresivo es un tema central de estudio. Se sabe, por ejemplo, que decidir si dos expresiones regulares arbitrarias describen el mismo conjunto de cadenas es difícil, mientras que hacer lo mismo para gramáticas arbitrarias independientes del contexto es completamente imposible . Sin embargo, todavía se puede decidir de manera eficiente si una cadena dada está en el conjunto.
Para los formalismos más expresivos, este problema puede ser más difícil o incluso indecidible. Para un formalismo completo de Turing , como las gramáticas formales arbitrarias , no solo este problema, sino toda propiedad no trivial relativa al conjunto de cadenas que describen es indecidible, un hecho conocido como el teorema de Rice .
También hay algunos resultados sobre la concisión; por ejemplo, los autómatas finitos no deterministas y las gramáticas regulares son más concisas que las expresiones regulares, en el sentido de que estas últimas pueden traducirse a las primeras sin un aumento en tamaño (es decir, en O(1) ), mientras que lo inverso no es posible.
Consideraciones similares se aplican a los formalismos que describen no conjuntos de cadenas, sino conjuntos de árboles (por ejemplo, los lenguajes de esquema XML ), de gráficos u otras estructuras.
La teoría de bases de datos se ocupa, entre otras cosas, de las consultas a bases de datos , es decir, fórmulas que, dado el contenido de una base de datos, especifican cierta información que se debe extraer de ella. En el paradigma predominante de bases de datos relacionales , el contenido de una base de datos se describe como un conjunto finito de relaciones matemáticas finitas; las consultas booleanas, que siempre arrojan verdadero o falso , se formulan en lógica de primer orden .
Resulta que la lógica de primer orden carece de poder expresivo: no puede expresar ciertos tipos de consultas booleanas, por ejemplo, consultas que involucran cierre transitivo . [6] Sin embargo, agregar poder expresivo debe hacerse con cuidado: debe seguir siendo posible evaluar consultas con una eficiencia razonable, lo que no es el caso, por ejemplo, para la lógica de segundo orden . En consecuencia, surgió una literatura en la que se compararon muchos lenguajes de consulta y construcciones de lenguaje sobre la base del poder expresivo y la eficiencia, por ejemplo, varias versiones de Datalog . [7]
Se aplican consideraciones similares para los lenguajes de consulta sobre otros tipos de datos, por ejemplo, los lenguajes de consulta XML como XQuery .