Transformers는 본질적으로 간결하다
발행: (2026년 5월 5일 AM 05:03 GMT+9)
2 분 소요
원문: Hacker News
Source: Hacker News
Resources
Abstract
우리는 변환기의 개념을 기술하는 표현력의 척도로서 간결성(succinctness) 을 제안한다. 이를 위해 변환기가 유한 자동자와 Linear Temporal Logic (LTL) 공식과 같은 전통적인 형식 언어 표현보다 훨씬 더 간결하게 형식 언어를 나타낼 수 있다는 점에서 매우 표현력이 높다는 것을 증명한다. 이러한 표현력의 부수 효과로, 변환기의 속성 검증이 이론적으로 EXPSPACE‑complete 라는 사실을 보여준다(즉, 검증이 계산적으로 난해함).
Subjects
- Formal Languages and Automata Theory (cs.FL)
- Machine Learning (cs.LG)
- Logic in Computer Science (cs.LO)
Citation
arXiv:2510.19315 (cs.FL)
or arXiv:2510.19315v2 (cs.FL) for this version.
DOI
https://doi.org/10.48550/arXiv.2510.19315 (arXiv‑issued DOI via DataCite)
Submission history
- v1 – Wed, 22 Oct 2025 07:25:54 UTC (28 KB) – by Pascal Bergsträßer (view email)
- v2 – Thu, 23 Oct 2025 08:09:19 UTC (28 KB)