Выразительная сила (информатика) - Expressive power (computer science)
В компьютерной науке , то выразительная сила (называемая также выразительность или экспрессивность ) языка широта идей , которые могут быть представлены и сообщенных на этом языке. Чем выразительнее язык, тем большее разнообразие и количество идей он может использовать для выражения.
Например, в профиле языка выражений языка веб-онтологий (OWL2 EL) отсутствуют идеи (такие как отрицание), которые могут быть выражены в OWL2 RL (языке правил). Таким образом, можно сказать, что OWL2 EL обладает меньшей выразительной силой, чем OWL2 RL. Эти ограничения позволяют использовать более эффективные ( полиномиальное время ) рассуждения в OWL2 EL, чем в OWL2 RL. Таким образом, OWL2 EL использует некоторую выразительную силу в пользу более эффективных рассуждений (обработки языка представления знаний).
Описание информации
Термин « выразительная сила» может использоваться в разных значениях. Это может означать количество идей, выражаемых на этом языке:
- независимо от легкости ( теоретической выразительности )
- лаконично и оперативно ( практическая выразительность )
Первый смысл доминирует в областях математики и логики, которые имеют дело с формальным описанием языков и их значения, таких как формальная теория языка , математическая логика и алгебра процессов .
В неформальных дискуссиях этот термин часто относится ко второму значению или к обоим. Это часто имеет место при обсуждении языков программирования . Были предприняты попытки формализовать эти неформальные употребления этого термина.
Понятие выразительной силы всегда относится к определенному типу вещей, которые может описывать рассматриваемый язык, и этот термин обычно используется при сравнении языков, которые описывают один и тот же тип вещей или, по крайней мере, сравнимые виды вещей.
Дизайн языков и формализмов предполагает компромисс между выразительной силой и анализируемостью. Чем больше формализм может выразить, тем труднее понять, о чем говорят примеры формализма. На проблемы, связанные с принятием решений, становится труднее отвечать или они становятся совершенно неразрешимыми .
Примеры
В формальной теории языка
Теория формального языка в основном изучает формализмы для описания наборов строк, таких как контекстно-свободные грамматики и регулярные выражения . Каждый пример формализма, например каждая грамматика и каждое регулярное выражение, описывает определенный набор строк. В этом контексте выразительная сила формализма - это набор наборов строк, описываемых его экземплярами, а сравнение выразительной силы - это вопрос сравнения этих наборов.
Важным критерием для описания относительной выразительной силы формализмов в этой области является иерархия Хомского . Он говорит, например, что регулярные выражения , недетерминированные конечные автоматы и регулярные грамматики имеют одинаковую выразительную силу, в то время как контекстно-свободные грамматики обладают большей выразительностью ; это означает, что наборы наборов строк, описываемые первыми тремя формализмами, равны, и это собственное подмножество набора наборов строк, описываемых контекстно-независимыми грамматиками.
В этой области стоимость выразительной силы является центральной темой исследования. Известно, например, что решить, описывают ли два произвольных регулярных выражения один и тот же набор строк, сложно, в то время как сделать то же самое для произвольных контекстно-свободных грамматик совершенно невозможно . Однако по-прежнему можно эффективно решить, входит ли какая-либо данная строка в набор.
Для более выразительных формализмов эта проблема может быть более сложной или даже неразрешимой. Для полного формализма Тьюринга , такого как произвольные формальные грамматики , не только эта проблема, но и все нетривиальные свойства набора строк, которые они описывают, являются неразрешимыми, факт, известный как теорема Райса .
Есть также некоторые результаты по лаконичности; например, недетерминированные конечные автоматы и регулярные грамматики более лаконичны, чем регулярные выражения, в том смысле, что последние могут быть преобразованы в первые без увеличения размера (то есть в O (1) ), в то время как обратное невозможно.
Аналогичные соображения применимы к формализмам, которые описывают не наборы строк, а наборы деревьев (например, языки схем XML ), графов или других структур.
В теории баз данных
Теория баз данных связана, среди прочего, с запросами к базе данных , например с формулами, которые, учитывая содержимое базы данных, извлекают из нее определенную информацию. В преобладающей парадигме реляционной базы данных содержимое базы данных описывается как конечный набор конечных математических отношений; Логические запросы, которые всегда возвращают истину или ложь , формулируются в логике первого порядка .
Оказывается, логике первого порядка не хватает выразительной силы: она не может выражать определенные типы логических запросов, например запросы, включающие транзитивное замыкание . Однако добавление выразительной силы должно производиться с осторожностью: по-прежнему должна оставаться возможность оценивать запросы с разумной эффективностью, что не так, например, для логики второго порядка . В результате возникла литература, в которой многие языки запросов и языковые конструкции сравнивались по выразительной мощности и эффективности, например, различные версии Datalog .
Аналогичные соображения применимы к языкам запросов к другим типам данных, например к языкам запросов XML, таким как XQuery .