Обычные языки и постоянная сложность общения

9

Пусть будет языком, и определим как тогда и только тогда, когда , Я ищу ссылку для:LAfL:A×A{0,1}fL(x,y)=1xyL

Предложение. является регулярным, если детерминированная коммуникационная сложность постоянна.LfL

Другими словами, является регулярным, если существует протокол для двух игроков для такой, что функция ограничен константой, где \ {текст} Прдча (Р, х, у) имеет число бит , обменивается Алисой и Бобом когда Алиса получает й и Боб у , в соответствии с протоколом P .LPfL

nmax{comm(P,x,y):|xy|=n}
comm(P,x,y)xyP

Единственное место, которое я смог найти, - это диссертация Джорджа Хаузера в 1989 году, доступная здесь , где он также обобщает это для других распределений входных данных xy среди Алисы и Боба, так что число «сокращений» является постоянным.

Михаэль Кадилхак
источник
Возьмем нерегулярный язык C и определим L={cr:cC,r{0,1}|c|} . Тогда L имеет сложность связи O(1) , но она, конечно, не является регулярной. Что мне не хватает?
Игорь Шинкарь
@IgorShinkar: Я не уверен, что получил именно то, что вы там написали, но вы, похоже, намекаете на классическое доказательство того, что каждый язык с одним словом в длину может быть преобразован в язык с постоянной сложностью общения. Однако это предполагает, что Алиса и Боб получают ровно половину тестируемого слова; здесь нет такого предположения, и, с точки зрения соперничества, они должны решить проблему с учетом любого разделения входных данных. Это отвечает на ваш вопрос?
Михаэль Кадилхак
1
А ну понятно. Так что если для любого разбиения CC постоянна, то регулярна. L
Игорь Шинкарь

Ответы:

3

Для вас есть «Коммуникационная сложность», Eyal Kushilevitz in Advances in Computers, том 44, 1997 ( http://www.sciencedirect.com/science/article/pii/S0065245808603423 ).

Вы также можете найти раздел «Сложность связи и иерархия Хомского» в книге Юрия Хромковича «Сложность связи и параллельные вычисления», где она доказана. Может быть, также доказано где-то в книге, но я не могу найти его здесь. Кажется, самое близкое - это упражнение 5.2.5.2, но это всего лишь упражнение (см. Также всю главу 5, в которой подробно изучается конечный автомат, но я не думаю, что он явно отвечает на ваш вопрос).

Что бы это ни стоило, доказательство обоих направлений выглядит легко, поэтому я думаю, что если вам нужно это в статье, вы можете быстро набросать его: для , возьмите конечный автомат для и заметьте, что Алисе достаточно сообщить состояние, которого она достигает после прочтения ее части ввода. Затем Боб заканчивает моделирование в автоматах. Для , если у вас есть протокол, ограниченный константой, то имеет конечное число частных что является хорошо известной характеристикой регулярных языков ,LLw1L={u:wuL}

holf
источник
Большое спасибо за ваш вклад. Я согласен, что это легкий и естественный результат, и, вероятно, его следует считать фольклором. Я на самом деле знаю две ссылки, которые вы даете довольно хорошо, и, так же, как вы, не могли найти там протокол, который я рассматриваю выше. Поскольку этот вопрос является «запросом-рекомендацией», я боюсь, что не могу принять ваш ответ на данный момент.
Михаэль Кадилхак
Я знаю, но это было слишком долго для комментария, и я думаю, что все еще стоит упомянуть, что по крайней мере один способ явно доказан в литературе. Я дам вам знать, если я наткнусь на доказательство!
Holf
Очень ценится! :-)
Михаэль Кадилхак