표현력(컴퓨터 과학)

Expressive power (computer science)

컴퓨터 공학에서 언어표현력(표현력 또는 표현력이라고도 함)은 그 언어로 표현되고 전달될 수 있는 아이디어의 폭이다.언어가 표현력이 더 높을수록 표현하기 위해 사용될 수 있는 아이디어의 다양성과 양은 더 커집니다.

를 들어 Web Ontology Language Expression Language Profile(OWL2 EL)에는 OWL2 RL(규칙 언어)로 표현할 수 있는 아이디어(부정 등)가 없습니다.따라서 OWL2 EL은 OWL2 RL보다 표현력이 낮다고 할 수 있다.이러한 제한은 OWL2 RL보다 OWL2 EL에서 더 효율적인 (다항 시간) 추론을 가능하게 한다.따라서 OWL2 EL은 보다 효율적인 추론(지식 표현 언어 처리)을 위해 표현력을 교환합니다.[1]

정보 설명

표현력이라는 용어는 다양한 의미와 함께 사용될 수 있다.이는 해당 [2]언어로 표현 가능한 아이디어의 척도를 의미할 수 있습니다.

  • 용이성에 관계없이(이론적 표현력)
  • 간결하고 쉽게(표현성을 높임)

첫 번째 감각은 형식 언어 이론, 수리 논리학, 프로세스 [2]대수학과 같은 언어와 그 의미에 대한 공식적인 설명을 다루는 수학과 논리 영역에서 지배적이다.

비공식 토론에서 이 용어는 종종 두 번째 의미 또는 두 가지 의미를 모두 가리킵니다.이것은 프로그래밍 언어를 [3][page needed]논할 때 흔히 있는 일입니다.이러한 비공식적 [4]용어의 사용을 공식화하기 위한 노력이 이루어졌다.

표현력의 개념은 항상 문제의 언어가 묘사할 수 있는 특정한 종류의 것에 상대적이며, 이 용어는 보통 같은 종류의 것 또는 적어도 비슷한 종류의 [4]것들을 묘사하는 언어들을 비교할 때 사용된다.

언어와 형식주의의 설계에는 표현력과 분석 능력 사이의 트레이드오프가 수반됩니다.형식주의가 더 많이 표현할 수 있을수록, 형식주의의 예가 무엇을 말하는지를 이해하는 것은 더 어려워진다.의사 결정 문제는 대답하기 어렵거나 완전히 결정[5]수 없게 된다.

형식 언어 이론에서

형식 언어 이론은 문맥이 없는 문법정규 표현과 같은 문자열 집합을 설명하기 위한 형식주의를 주로 연구합니다.형식주의의 각 인스턴스(예: 각 문법 및 각 정규 표현)는 특정 문자열 집합을 기술합니다.이 맥락에서 형식주의의 표현력은 그 인스턴스가 기술하는 문자열 집합이며, 표현력을 비교하는 것은 이들 집합을 비교하는 문제이다.

이 영역에서 형식주의의 상대적 표현력을 설명하는 중요한 척도는 촘스키 계층이다.예를 들어, 그것은 정규 표현, 비결정론적 유한 오토마톤정규 문법은 동일한 표현력을 갖는 반면, 문맥이 없는 문법은 더 크다; 이것이 의미하는 것은 처음 세 가지 형식에 의해 기술된 문자열 집합의 집합이 동일하고, 그리고 다음에 의해 기술된 문자열 집합의 적절한 집합이 동일하다는 것이다.문맥이 없는 문법

이 분야에서는 표현력의 비용이 연구의 중심 주제이다.예를 들어, 두 개의 임의의 정규식이 동일한 문자열 집합을 기술하는지 여부를 결정하는 것은 어렵지만, 임의의 문맥이 없는 문법에 대해서는 동일한 작업을 수행하는 것은 완전히 불가능하다고 알려져 있습니다.단, 세트에 지정된 문자열이 있는지 여부는 여전히 효율적으로 판단할 수 있습니다.

좀 더 표현적인 형식주의의 경우, 이 문제는 더 어렵거나 심지어 결정하지 못할 수도 있다.임의의 형식 문법과 같은 튜링 완전 형식주의에서는 이 문제뿐만 아니라, 그들이 설명하는 문자열의 집합과 관련된 모든 중요한 특성은 결정 불가능하며, 이는 라이스의 정리라고 알려져 있다.

간결성에 대한 결과도 있다. 예를 들어, 비결정적 상태 기계와 정규 문법은 정규 표현보다 간결하다. 정규 표현은 크기가 확대되지 않고(즉, O(1)에서) 전자로 번역될 수 있지만, 그 반대는 불가능하다.

유사한 고려사항은 문자열 집합이 아니라 트리 집합(예: XML 스키마 언어), 그래프 또는 기타 구조를 설명하는 형식에도 적용됩니다.

데이터베이스 이론에서

데이터베이스 이론은 무엇보다도 데이터베이스 쿼리, 예를 들어 데이터베이스의 내용이 주어진 경우 특정 정보를 추출하는 공식과 관련이 있습니다.지배적인 관계형 데이터베이스 패러다임에서 데이터베이스의 내용은 유한한 수학적 관계의 집합으로 설명된다.항상 참 또는 거짓을 산출하는 부울 쿼리는 1차 논리로 공식화된다.

1차 로직은 표현력이 부족한 것으로 드러났다. 즉, 특정 유형의 부울 쿼리를 표현할 수 없다(예: 전이 [6]폐쇄를 포함하는 쿼리).단, 표현력을 추가하는 것은 신중하게 수행해야 합니다.조회를 합리적으로 효율적으로 평가할 수 있어야 합니다.예를 들어 2차 논리에서는 그렇지 않습니다.그 결과, 다양한 버전[7]데이터로그와 같은 표현력과 효율성에 대해 많은 질의 언어와 언어 구조를 비교한 문헌이 생겨났습니다.

XQuery와 같은 XML 쿼리 언어 등 다른 유형의 데이터 쿼리 언어에도 유사한 고려 사항이 적용됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Grau, Bernardo Cuenca; Horrocks, Ian; Motik, Boris; Parsia, Bijan; Patel-Schneider, Peter; Sattler, Ulrike (2008). "OWL 2: The next step for OWL". Web Semantics: Science, Services and Agents on the World Wide Web. 6 (4): 309–322. doi:10.1016/j.websem.2008.05.001. ISSN 1570-8268.
  2. ^ a b Farmer, William (2007). "Chiron: A multi-paradigm logic". In R. Matuszewski; A. Zalewska (eds.). From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Studies in Logic, Grammar and Rhetoric. pp. 1–19. ISBN 978-83-7431-128-1.
  3. ^ AbelsonSussman컴퓨터 프로그램 구조와 해석
  4. ^ a b Felleisen, Matthias (1991-12-01). "On the expressive power of programming languages". Science of Computer Programming. 17 (1): 35–75. doi:10.1016/0167-6423(91)90036-W.
  5. ^ Okhotin, Alexander (December 2005). "Unresolved systems of language equations: Expressive power and decision problems". Theoretical Computer Science. 349 (3): 283–308. doi:10.1016/j.tcs.2005.07.038.
  6. ^ 세르게이 아비테불, 리처드 B. Hull, Victor Vianu: 데이터베이스의 기초.애디슨 웨슬리, 1995년
  7. ^ Evgeny Dantsin, Thomas Eiter, Georg GottlobAndrei Voronkov: 논리 프로그래밍의 복잡성과 표현력.ACM 계산생존 33(3): 374-425(2001)