Кузьмин Е.В., Соколов В.А. Автоматные счетчиковые машины

Яросл. гос. ун-т им. П. Г. Демидова. — Ярославль : ЯрГУ, 2012. — 81 c. — ISBN: 978-5-8397-0893-8.Монография посвящена автоматным счетчиковым машинам и тем формальным языкам, которые способны распознавать/задавать эти абстрактные математические машины. Приведенные здесь результаты представляют интерес как для теории формальных моделей вычислений, так и для теории формальных языков, поскольку автоматные счетчиковые машины (и соответственно их языки) занимают особое положение в иерархии формализмов в границах от конечных автоматов до машин Тьюринга (счетчиковых машин Минского). Свойства автоматных счетчиковых машин изучаются с привлечением теории правильных квазипорядков и теории вполне структурированных систем переходов, которые оказываются полезными для решения задач анализа семантических свойств различных формальных моделей, являющихся более слабыми по вычислительной мощности (выразительной способности), чем машины Тьюринга.Предисловие.
Счетчиковые машины.
Машины Тьюринга.
Алгоритмические проблемы.
Счетчиковые машины Минского.Двухсчетчиковые машины.
Неразрешимые проблемы и метод сведения.
Двухголовочные автоматы.Однорегистровые машины.
Однорегистровые машины.
Теоремы по проблеме «входа».
Теоремы по проблеме «выхода».
О вычислимых функциях.Структурированные системы переходов.
Квазипорядок.
Структурированные системы переходов.
Автоматные системы переходов.Автоматные счетчиковые машины.
Слабые счетчиковые машины.
Автоматные счетчиковые машины.
Автоматные трехсчетчиковые машины.Языки автоматных счетчиковых машин.
Автоматная счетчиковая машина.
Проблемы пустоты и распознавания слов.
Свойства замкнутости.
Проблемы включения и равенства языков.Литература.