В настоящее время я занимаюсь исследованиями Формального языка, в которых участвуют классы языков выше обычного, но ниже контекста. Я смотрю на такие вещи, как машины с множеством счетчиков с ограниченным обращением, счетчики с одним стеком, детерминированные КЛЛ и т. Д.
Мне интересно, знает ли кто-нибудь хорошую книгу или обзорную статью, в которой описываются свойства этих языков. Большая часть того, на что я смотрю, слишком неясна или слишком нова, чтобы быть в моей книге Хопкрофта-Уллмана, даже в издании 1979 года.
В основном я ищу, какие языковые классы содержатся друг в друге, свойства замыкания этих языков и разрешимость основных проблем (F-задачи) на этих языках.
Некоторые примеры вещей, которые я бы посмотрел в этой ссылке:
- Все ли языки, принятые машинами с множеством счетчиков с ограничением обращения, также принимаются машинами с одиночным счетчиком без ограничений?
- Закрыты ли детерминированные языки, ограниченные обращением MultiCounter, при объединении слева и справа?
- Является ли универсальность разрешимой для машин с одним счетчиком.
Это только примеры вопросов, у меня есть много других вопросов, которые возникают в моей повседневной работе.
В качестве отправной точки я попытался отследить, какие документы ссылаются на «Машины с множественными столкновениями, ограниченные обращением, и проблемы их решения» Оскара Ибарры, но не нашел много.
Ответы:
Не стандартные темы, нет. И извините, у меня нет общего обзора.
Тем не менее, я хотел бы взглянуть на кандидатскую диссертацию Клауса Рейнхардта, по крайней мере, для картины различных семей, которые живут в этой области. См. Стр. 64 для диаграммы зоопарка. По мотивам Петри Нетс с дугой-ингибитором Рейнхардт изучает приоритетные мультисчетчики с ограничениями на время проведения нулевых тестов. Нетривиальный.
Кстати, ваш последний пример вопроса обсуждался на этом форуме пользователем Сэмом Джонсом. Еще одна ссылка на Ибарру.
источник