트랜스포머는 본질적으로 간결함

요약

본 논문은 개념을 설명하는 모델로서 트랜스포머가 가진 표현력을 측정하기 위해 '간결성(succinctness)'이라는 지표를 제안합니다. 연구진은 트랜스포머가 유한 오토마타나 LTL 공식 같은 표준 형식 언어보다 훨씬 간결하게 형식 언어를 표현할 수 있음을 증명했습니다. 이로 인해, 트랜스포머의 속성을 검증하는 문제는 계산적으로 매우 어려운(EXPSPACE-complete) 문제임이 밝혀졌습니다.

핵심 포인트

• 트랜스포머 모델의 표현력을 측정하기 위해 '간결성' 지표를 도입함.
• 트랜스포머는 유한 오토마타나 LTL 공식 같은 표준 형식 언어보다 더 간결하게 형식 언어를 인코딩할 수 있음.
• 이러한 높은 표현력의 결과로, 트랜스포머 속성 검증 문제는 EXPSPACE-complete라는 매우 어려운 계산 복잡도를 가짐.