Пусть будет языком, и определим как тогда и только тогда, когда , Я ищу ссылку для:
Предложение. является регулярным, если детерминированная коммуникационная сложность постоянна.
Другими словами, является регулярным, если существует протокол для двух игроков для такой, что функция ограничен константой, где \ {текст} Прдча (Р, х, у) имеет число бит , обменивается Алисой и Бобом когда Алиса получает й и Боб у , в соответствии с протоколом P .
Единственное место, которое я смог найти, - это диссертация Джорджа Хаузера в 1989 году, доступная здесь , где он также обобщает это для других распределений входных данных среди Алисы и Боба, так что число «сокращений» является постоянным.
reference-request
communication-complexity
regular-language
Михаэль Кадилхак
источник
источник
Ответы:
Для вас есть «Коммуникационная сложность», Eyal Kushilevitz in Advances in Computers, том 44, 1997 ( http://www.sciencedirect.com/science/article/pii/S0065245808603423 ).⇒
Вы также можете найти раздел «Сложность связи и иерархия Хомского» в книге Юрия Хромковича «Сложность связи и параллельные вычисления», где она доказана. Может быть, также доказано где-то в книге, но я не могу найти его здесь. Кажется, самое близкое - это упражнение 5.2.5.2, но это всего лишь упражнение (см. Также всю главу 5, в которой подробно изучается конечный автомат, но я не думаю, что он явно отвечает на ваш вопрос).⇐
Что бы это ни стоило, доказательство обоих направлений выглядит легко, поэтому я думаю, что если вам нужно это в статье, вы можете быстро набросать его: для , возьмите конечный автомат для и заметьте, что Алисе достаточно сообщить состояние, которого она достигает после прочтения ее части ввода. Затем Боб заканчивает моделирование в автоматах. Для , если у вас есть протокол, ограниченный константой, то имеет конечное число частных что является хорошо известной характеристикой регулярных языков ,⇒ L ⇐ L w−1L={u:wu∈L}
источник