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