Трансформеры по своей природе сжаты

Исследователи предложили меру выразительной силы трансформеров через призму сжатости описания. Доказано, что модели могут представлять формальные языки значительно компактнее, чем конечные автоматы или формулы линейной темпоральной логики. В качестве следствия показано, что проверка свойств трансформеров вычислительно сложна и относится к классу EXPSPACE-complete.