Сложность зоопарка для одинарных языков

25

Конечно, некоторые результаты сложности могут рухнуть для унарных языков, но мне интересно, есть ли где-нибудь опрос, обобщающий известные результаты в этом случае: своего рода зоопарк сложности для унарных языков. Знаете ли вы о такой ссылке?

cc.complexity-theory reference-request big-list J.-E. Штырь
источник
7
Конечно, неизвестно, существует ли NP-полный унарный язык. Смотрите это больше: en.wikipedia.org/wiki/…
Райан
Не совсем то, что вы ищете, но здесь есть мини-зоопарк с некоторыми языками, приводимыми к унарным языкам. arxiv.org/abs/1212.3282
Найл Мерфи

Ответы:

23

Ссылок в стиле зоопарка пока нет, но недавнее автоматное теоретическое исследование Джованни Пигиццини было мне полезно, особенно слайды из его выступления.

  • Джованни Пигиццини, Исследования автоматов и языков над унарным алфавитом , CIAA 2014. doi: 10.1007 / 978-3-319-08846-4_3
Андраш Саламон
источник
12

Один интересный вопрос о классах сложности по унарному алфавиту, которого нет в приведенных выше ссылках, - это сила класса Валианта #P 1 , класса подсчета проблем по унарному алфавиту (см. Http://epubs.siam.org/doi/ абс / 10.1137 / 0208032 ). О его мощи мало что известно, хотя он имеет естественные полные проблемы и, как и унарные языки, имеет схемы полиномиального размера.

Пол Бим
источник