Выразительная сила (информатика) - Expressive power (computer science)

В Информатика, то выразительная сила (также называемый выразительность или же выразительность) языка - это широта идей, которые могут быть представлены и переданы на этом языке. Чем выразительнее язык, тем большее разнообразие и количество идей он может использовать для выражения.

Например, Язык веб-онтологий В профиле языка выражений (OWL2 EL) отсутствуют идеи (например, отрицание), которые могут быть выражены в OWL2 RL (языке правил). Таким образом, можно сказать, что OWL2 EL имеет меньше выразительная сила чем OWL2 RL. Эти ограничения позволяют более эффективно (полиномиальное время ) рассуждения в OWL2 EL, чем в OWL2 RL. Таким образом, OWL2 EL использует некоторую выразительную силу в пользу более эффективных рассуждений (обработки языка представления знаний).[1]

Описание информации

Период, термин выразительная сила может использоваться с разными значениями. Это может означать количество идей, выражаемых на этом языке:[2]

  • независимо от легкости (теоретическая выразительность)
  • кратко и легко (практическая выразительность)

Первое чувство доминирует в областях математика и логика которые касаются формального описания языков и их значения, например формальная теория языка, математическая логика и алгебра процессов.[2]

В неформальных дискуссиях этот термин часто относится ко второму значению или к обоим. Это часто бывает при обсуждении языки программирования.[3][страница нужна ] Были предприняты попытки формализовать эти неформальные употребления этого термина.[4]

Понятие выразительной силы всегда относится к определенному типу вещей, которые может описывать рассматриваемый язык, и этот термин обычно используется при сравнении языков, которые описывают один и тот же тип вещей или, по крайней мере, сравнимые виды вещей.[5]

Дизайн языков и формализмов предполагает компромисс между выразительностью и анализируемостью. Чем больше формализм может выразить, тем труднее понять, что говорят примеры формализма. Проблемы с решением становится труднее отвечать или полностью неразрешимый.[6]

Примеры

В формальной теории языка

Теория формального языка в основном изучает формализмы для описания наборов строк, таких как контекстно-свободные грамматики и обычные выражения. Каждый пример формализма, например каждая грамматика и каждое регулярное выражение описывает определенный набор строк. В этом контексте выразительная сила формализма - это набор наборов строк, которые описывают его экземпляры, а сравнение выразительной силы - это вопрос сравнения этих наборов.

Важным критерием для описания относительной выразительной силы формализмов в этой области является Иерархия Хомского. Он говорит, например, что обычные выражения, недетерминированные конечные автоматы и регулярные грамматики обладают равной выразительной силой, в то время как контекстно-свободные грамматики лучше; это означает, что наборы наборов строк, описываемые первыми тремя формализмами, равны, и это собственное подмножество набора наборов строк, описываемых контекстно-независимыми грамматиками.

В этой области стоимость выразительной силы является центральной темой исследования. Известно, например, что сложно решить, описывают ли два произвольных регулярных выражения один и тот же набор строк, в то время как сделать то же самое для произвольных контекстно-свободных грамматик сложно. совершенно невозможно. Тем не менее, все еще можно эффективно решить, входит ли какая-либо данная строка в набор.

Для более выразительных формализмов эта проблема может быть более сложной или даже неразрешимой. Для Тьюринг завершен формализм, например произвольный формальные грамматики, не только эта проблема, но каждый нетривиальное свойство набора строк, которые они описывают, неразрешимо, факт, известный как Теорема Райса.

Есть также некоторые результаты по лаконичности; например, недетерминированные конечные автоматы и регулярные грамматики более лаконичны, чем регулярные выражения, в том смысле, что последние могут быть преобразованы в первые без увеличения размера (т.е. О (1) ), а обратное невозможно.

Аналогичные соображения применимы к формализмам, которые описывают не наборы строк, а наборы деревьев (например, Языки схемы XML ), графов или других структур.

В теории баз данных

Теория баз данных касается, среди прочего, запросы к базе данных, например формулы, которые, учитывая содержимое базы данных, извлекают из нее определенную информацию. В преобладающем реляционная база данных парадигма, содержимое базы данных описывается как конечный набор конечных математических отношений; Логические запросы, которые всегда дают истинный или же ложный, сформулированы в логика первого порядка.

Оказывается, что логика первого порядка не обладает выразительной силой: он не может выражать определенные типы логических запросов, например запросы с участием переходное закрытие.[7] Однако добавление выразительной силы должно производиться с осторожностью: по-прежнему должна оставаться возможность оценивать запросы с разумной эффективностью, что не так, например, для логика второго порядка. Следовательно, возникла литература, в которой многие языки запросов и языковые конструкции сравнивались по выразительной мощности и эффективности, например различные версии Лог данных.[8]

Аналогичные соображения применимы к языкам запросов для других типов данных, например Языки запросов XML, такие как XQuery.

Смотрите также

Рекомендации

  1. ^ Грау, Бернардо Куэнка; Хоррокс, Ян; Мотик, Борис; Парсия, Биджан; Патель-Шнайдер, Питер; Саттлер, Ульрике (2008). «OWL 2: Следующий шаг для OWL». Веб-семантика: наука, услуги и агенты во всемирной паутине. 6 (4): 309–322. Дои:10.1016 / j.websem.2008.05.001. ISSN  1570-8268.
  2. ^ а б Фермер, Уильям (2007). «Хирон: мультипарадигмальная логика». У Р. Матушевского; А. Залевская (ред.). От прозрения к доказательству: Праздник в честь Анджея Трибулца. Исследования по логике, грамматике и риторике. С. 1–19. ISBN  978-83-7431-128-1.
  3. ^ Структура и интерпретация компьютерных программ, к Абельсон и Сассман
  4. ^ Фелляйзен, Маттиас (1991-12-01). «О выразительной силе языков программирования». Наука компьютерного программирования. 17 (1): 35–75. Дои:10.1016 / 0167-6423 (91) 90036-В. ISSN  0167-6423.
  5. ^ Фелляйзен, Матиас (декабрь 1991 г.). «О выразительной силе языков программирования». Наука компьютерного программирования. 17 (1–3): 35–75. Дои:10.1016 / 0167-6423 (91) 90036-В.
  6. ^ Охотин, Александр (декабрь 2005 г.). «Неразрешенные системы языковых уравнений: проблемы выразительной силы и решения». Теоретическая информатика. 349 (3): 283–308. Дои:10.1016 / j.tcs.2005.07.038.
  7. ^ Серж Абитебул, Ричард Б. Халл, Виктор Виану: Основы баз данных. Аддисон-Уэсли, 1995.
  8. ^ Евгений Данцин, Томас Эйтер, Георг Готтлоб, и Андрей Воронков: Сложность и выразительная сила логического программирования. ACM Comput. Surv. 33 (3): 374-425 (2001).