Ссылка на языки Dyck, являющаяся

12

Языки Dyck определяются следующей грамматикой S S SDyck(k) над множеством символов { ( 1 , , ( k , ) 1 , , ) k } . Интуитивно понятно, что языки Dyck - это языки сбалансированных скобок k различного типа. Например, (

SSS|(1S)1||(kS)k|ϵ
{(1,,(k,)1,,)k}k находится в D y c k ( 2 ), но (([])()Dyck(2) нет.([)]

В газете

Динамические алгоритмы для языков Дейка , Frandsen, Husfeldt, Miltersen, Rauhe, and Skyum, 1995,

утверждается, что следующим результатом является фольклор:

является T C 0 -полным присокращениях A C 0 .Dyck(k)TC0AC0

Известна ли какая-либо ссылка на вышеуказанную претензию? В частности, я ищу любые результаты, которые показывают по крайней мере одно из следующего:

  • находится в T C 0 для произвольного k .Dyck(k)TC0k
  • является T C 0 -твердым для произвольного k .Dyck(k)TC0k

Ближайшая статья, которую я могу найти,

Би-липшицева биекция между булевым кубом и шаром Хэмминга , Бенджамини, Коэн и Шинкарь, 2013

Dyck(1)TC0

Любые связанные документы приветствуются. Благодарность!

Сянь-Чжи Чан 張顯 之
источник

Ответы:

6

AC0MajorityDyck(1)MajorityAC0Dyck(k)k1ANDORNOTDyck(1)


  • x{0,1}nMajority
  • y{0,1}2n0((1()
  • i=1,,n/2ziy2izi=y)2i
  • ziDyck(1)i=1,,n/2

ziOR

MajorityziDyck(1)weight(x)=ni

Игорь Шинкарь
источник
Благодарю. Знаете ли вы какие-либо бумаги, которые содержат результат выше? (Это нормально, если статья не оригинальная / самая ранняя, я пытаюсь проследить историю.)
Сянь-Чжи Чанг 14 之
Хммм ... по какой-то причине я предположил, что аналогичное сокращение появилось в той статье Линча ... Я не знаю других ссылок для этого.
Игорь Шинкарь