Вопросы с тегом «unary-languages»

Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима?

Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима? Проблема пустотности для вычислительной модели (например, автомат конечного состояния, автомат с переменным нажатием, квантовый автомат с ограниченной ошибкой со счетчиком, детерминированный LBA и т. Д.) Состоит в...

Могут ли односторонние чередующиеся автоматы с одним счетчиком распознавать некоторые унарные нерегулярные языки?

Односторонние чередующиеся нажимные автоматы (1APDA) могут распознавать любой язык в (Чередование, Чандра, Козен и Стокмейер, 1981) . Заменив хранилище 1APDA со счетчиком, можно получить односторонний чередующийся автомат с одним счетчиком (1ACA). Мой вопрос о 1ACA на унарных языках.Д ТяMЕ( 2O ( n...