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