트리접합문법

Tree-adjoining grammar

TAG(Tree-Adjoining Grammar)는 Aravind Joshi에 의해 정의된 문법 형식주의입니다.트리 결합 문법은 문맥이 없는 문법과 다소 유사하지만, 다시 쓰기의 기본 단위는 기호보다는 트리입니다.문맥이 없는 문법에는 기호를 다른 기호 문자열로 다시 쓰는 규칙이 있는 반면, 트리 결합 문법에는 트리의 노드를 다른 트리로 다시 쓰는 규칙이 있습니다(나무(그래프 이론) 및 트리(데이터 구조 참조).

역사

TAG는 Zellig [2]Harris의 "문자열 문법"인 부가 문법(AG)[1] 패밀리에 대한 조시와 그의 학생들에 의한 조사에서 비롯되었습니다.AG는 언어의 외중심적 특성을 자연스럽고 효과적으로 다루지만 내중심적 구성의 좋은 특성을 가지고 있지는 않습니다. 즉, 그 반대는 개서 문법, 즉 구구조 문법(PSG)에 해당됩니다.1969년, 조시는 두 종류의 규칙을 혼합함으로써 이러한 상호보완성을 이용하는 문법군을 도입했다.부가 규칙 문자열 어휘를 생성하기 위해서는 몇 가지 매우 간단한 개서 규칙만으로 충분합니다.이 어족은 촘스키-슐첸버거 계층과는 다르지만 흥미롭고 언어적으로 관련된 방식으로 [3]교차한다.중앙 문자열과 보조 문자열은 의존 문법에 의해 생성될 수 있으며,[4] 시스템 전체를 다시 쓰는 제한을 피할 수 있습니다.[5]

묘사

TAG의 규칙은 풋노드로 불리는 특별한 리프노드를 가진 트리로 단어에 고정됩니다.TAG에는 초기 트리(종종 'displaystyle\로 표시됨)와 보조 트리('β의 두 가지 기본 트리가 있습니다.초기 트리는 기본 원자가 관계를 나타내며 보조 트리는 [6]재귀가 허용됩니다.보조 트리에는 루트(상단) 노드와 풋 노드가 동일한 기호로 레이블이 지정됩니다.파생은 치환 또는 부가 중 하나를 통해 결합되는 초기 트리에서 시작합니다.치환은 프런티어노드를 최상위 노드의 라벨이 같은 다른 트리로 바꿉니다.보조 트리의 루트/풋 라벨은 인접한 노드의 라벨과 일치해야 합니다.따라서 인접은 보조 트리를 다른 [4]트리의 중앙에 삽입하는 효과를 가져올 수 있습니다.

다른 종류의 TAG에서는 멀티 컴포넌트 트리, 여러 개의 풋노드가 있는 트리 및 기타 확장을 사용할 수 있습니다.

복잡성과 응용 프로그램

트리 결합 문법은 문맥이 없는 문법에 비해 강력하지만 문맥이 없는 선형 재작성 시스템[note 1],[7] 색인화 또는 문맥에 민감한 문법에 비해서는 강력하지 않습니다.

TAG는 정사각형 언어(일부 임의의 문자열이 반복되는 경우) 및 { c µ n} { \ } bn c^ n d^ 1 \n)을 기술할 수 있습니다.이러한 유형의 처리는 내장된 푸시다운 자동화로 나타낼 수 있습니다.큐브(즉, 복잡한 문자열)가 있거나 길이가 동일한 4개 이상의 문자열이 있는 언어는 트리 결합 문법에 의해 생성될 수 없습니다.

이러한 이유로, 나무 결합 문법은 종종 약간의 문맥에 민감한 것으로 설명됩니다.이러한 문법 클래스는 자연어를 모델링할 수 있을 정도로 강력하면서도 일반적인 [8]경우 효율적으로 해석할 수 있는 것으로 추측됩니다.

등가

Vijay-Shanker와 Weir(1994)[9]는 선형 색인 문법, 조합 범주 문법, 트리 결합 문법 및 헤드 문법이 모두 동일한 문자열 언어를 정의한다는 점에서 약하게 동등한 형식주의임을 입증한다.

어휘화된

LTAG(Lexicalized Tree-Adding Grammars)는 각 기본 트리(초기 또는 보조)가 어휘 항목과 연관된 TAG의 변형입니다.영어의 어휘화된 문법은 펜실베니아 [5]대학 인지과학 연구소의 XTAG 연구 그룹에 의해 개발되었다.

메모들

  1. ^ 각 트리 결합 문법에 대해 동일한 언어를 생성하는 선형 색인 문법을 찾을 수 있기 때문에, 아래를 참조하고, 후자에 대해서는 약하게 등가(적절한) 색인 문법을 찾을 수 있습니다. 차례로 색인 문법#계산 파워를 참조하십시오.

레퍼런스

  1. ^ Joshi, Aravind; S. R. Kosaraju; H. Yamada (1969). "String Adjunct Grammars". Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말) Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, H. M. (1972), "String Adjunct Grammars: I. Local and Distributed Adjunction", Information and Control, 21 (2): 93–116, doi:10.1016/S0019-9958(72)90051-4 Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, H. M. (1972), "String Adjunct Grammars: II. Equational Representation, Null Symbols, and Linguistic Relevance", Information and Control, 21 (3): 235–260, doi:10.1016/S0019-9958(72)80005-6
  2. ^ Harris, Zellig S. (1962). String analysis of sentence structure. Papers on Formal Linguistics. Vol. 1. The Hague: Mouton & Co.
  3. ^ Joshi, Aravind (1969). "Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance". Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  4. ^ a b Joshi, Aravind; Owen Rambow (2003). "A Formalism for Dependency Grammar Based on Tree Adjoining Grammar" (PDF). Proceedings of the Conference on Meaning-Text Theory.
  5. ^ a b "A Lexicalized Tree Adjoining Grammar for English".
  6. ^ Jurafsky, Daniel; James H. Martin (2000). Speech and Language Processing. Upper Saddle River, NJ: Prentice Hall. p. 354.
  7. ^ 칼마이어, 로라(2010).문맥을 벗어난 구문 분석 - 문법이 필요 없습니다.스프링거.여기: 페이지 215-216
  8. ^ Joshi, Aravind (1985). "How much context-sensitivity is necessary for characterizing structural descriptions". In D. Dowty; L. Karttunen; A. Zwicky (eds.). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives. New York, NY: Cambridge University Press. pp. 206–250. ISBN 9780521262033.
  9. ^ 비제이 생커, K, 위어, 데이비드 J. 1994년문맥이 없는 문법의 네 가지 확장의 등가성.수학 시스템 이론 27(6): 511~546.

외부 링크