Языки Dyck определяются следующей грамматикой S → S S над множеством символов { ( 1 , … , ( k , ) 1 , … , ) k } . Интуитивно понятно, что языки Dyck - это языки сбалансированных скобок k различного типа. Например, (
В газете
Динамические алгоритмы для языков Дейка , Frandsen, Husfeldt, Miltersen, Rauhe, and Skyum, 1995,
утверждается, что следующим результатом является фольклор:
является T C 0 -полным присокращениях A C 0 .
Известна ли какая-либо ссылка на вышеуказанную претензию? В частности, я ищу любые результаты, которые показывают по крайней мере одно из следующего:
- находится в T C 0 для произвольного k .
- является T C 0 -твердым для произвольного k .
Ближайшая статья, которую я могу найти,
Би-липшицева биекция между булевым кубом и шаром Хэмминга , Бенджамини, Коэн и Шинкарь, 2013
Любые связанные документы приветствуются. Благодарность!