Ekspresyjna moc (informatyka)
W informatyce siła wyrazu (zwana także wyrazistością lub wyrazistością ) języka to zakres idei , które mogą być reprezentowane i przekazywane w tym języku. Im bardziej wyrazisty jest język, tym większa różnorodność i ilość idei, które może reprezentować.
Na przykład profil języka wyrażeń Web Ontology Language (OWL2 EL) nie zawiera idei (takich jak negacja), które można wyrazić w OWL2 RL (język reguł). Można zatem powiedzieć, że OWL2 EL ma mniejszą moc ekspresji niż OWL2 RL. Te ograniczenia pozwalają na bardziej wydajne ( czas wielomianowy ) rozumowanie w OWL2 EL niż w OWL2 RL. Tak więc OWL2 EL zamienia pewną moc ekspresji na bardziej efektywne rozumowanie (przetwarzanie reprezentacji wiedzy ).
Opis informacji
Termin moc ekspresyjna może być używany w wielu znaczeniach. Może to oznaczać miarę idei dających się wyrazić w tym języku:
- niezależnie od łatwości ( ekspresyjność teoretyczna )
- zwięźle i chętnie ( praktyczna ekspresja )
Pierwszy sens dominuje w obszarach matematyki i logiki , które zajmują się formalnym opisem języków i ich znaczeniem, takich jak formalna teoria języka , logika matematyczna i algebra procesów .
W nieformalnych dyskusjach termin ten często odnosi się do drugiego zmysłu lub do obu. Dzieje się tak często podczas omawiania języków programowania . [ potrzebna strona ] Podjęto wysiłki w celu sformalizowania tych nieformalnych zastosowań tego terminu.
Pojęcie mocy ekspresyjnej zawsze odnosi się do określonego rodzaju rzeczy, które dany język może opisać, i termin ten jest zwykle używany do porównywania języków opisujących ten sam rodzaj rzeczy lub przynajmniej porównywalne rodzaje rzeczy.
Projektowanie języków i formalizmów wymaga kompromisu między mocą ekspresji a analizowalnością. Im więcej formalizm może wyrazić, tym trudniej zrozumieć, co mówią przykłady formalizmu. Problemy decyzyjne stają się trudniejsze do rozwiązania lub całkowicie nierozstrzygalne .
Przykłady
W formalnej teorii języka
Teoria języka formalnego zajmuje się głównie formalizmami opisującymi zestawy ciągów znaków, takimi jak gramatyki bezkontekstowe i wyrażenia regularne . Każdy przypadek formalizmu, np. każda gramatyka i każde wyrażenie regularne, opisuje określony zestaw ciągów znaków. W tym kontekście siła wyrazu formalizmu jest zbiorem zestawów ciągów znaków, które opisują jego instancje, a porównywanie siły wyrazu jest kwestią porównywania tych zestawów.
Ważnym miernikiem opisującym względną ekspresyjną siłę formalizmów w tym obszarze jest hierarchia Chomsky'ego . Mówi na przykład, że wyrażenia regularne , niedeterministyczne automaty skończone i gramatyki regularne mają taką samą moc wyrażania, podczas gdy gramatyka bezkontekstowa jest większa; oznacza to, że zbiory ciągów znaków opisane przez pierwsze trzy formalizmy są równe i stanowią właściwy podzbiór zbioru ciągów znaków opisanych przez gramatyki bezkontekstowe.
W tej dziedzinie koszt mocy ekspresyjnej jest głównym tematem badań. Wiadomo na przykład, że rozstrzygnięcie, czy dwa dowolne wyrażenia regularne opisują ten sam zestaw ciągów, jest trudne, a zrobienie tego samego dla dowolnych gramatyk bezkontekstowych jest całkowicie niemożliwe . Jednak nadal można skutecznie zdecydować, czy dany ciąg znajduje się w zestawie.
W przypadku bardziej wyrazistych formalizmów problem ten może być trudniejszy, a nawet nierozstrzygalny. Dla kompletnego formalizmu Turinga, takiego jak arbitralne gramatyki formalne , nie tylko ten problem, ale każda nietrywialna właściwość dotycząca zestawu ciągów, które opisują, jest nierozstrzygalna, co jest znane jako twierdzenie Rice'a .
Istnieją również wyniki dotyczące zwięzłości; na przykład niedeterministyczne maszyny stanowe i gramatyki regularne są bardziej zwięzłe niż wyrażenia regularne w tym sensie, że te drugie można przetłumaczyć na te pierwsze bez powiększania rozmiaru (tj. w O(1) ) , podczas gdy odwrotność nie jest możliwa.
Podobne rozważania dotyczą formalizmów, które opisują nie zbiory łańcuchów znaków, ale zbiory drzew (np. języki schematów XML ), grafów lub innych struktur.
W teorii baz danych
Teoria baz danych zajmuje się między innymi zapytaniami do baz danych , np. formułami, które na podstawie zawartości bazy danych wydobywają z niej określone informacje. W dominującym relacyjnych baz danych zawartość bazy danych jest opisywana jako skończony zbiór skończonych relacji matematycznych; Zapytania boolowskie, które zawsze zwracają prawdę lub fałsz , są formułowane w logice pierwszego rzędu .
Okazuje się, że logika pierwszego rzędu nie ma mocy ekspresyjnej: nie może wyrazić pewnych typów zapytań boolowskich, np. zapytań z domknięciem przechodnim . Jednak dodawanie mocy ekspresyjnej musi być wykonywane ostrożnie: nadal musi istnieć możliwość oceny zapytań z rozsądną wydajnością, co nie ma miejsca np. w przypadku logiki drugiego rzędu . W rezultacie powstała literatura, w której porównano wiele języków zapytań i konstrukcji językowych pod względem siły ekspresji i wydajności, np. różne wersje Datalogu .
Podobne uwagi dotyczą języków zapytań dotyczących innych typów danych, np. języków zapytań XML, takich jak XQuery .
