Автоматные счетчиковые машины

Description

Монография посвящена автоматным счетчиковым машинам и тем формальным языкам, которые способны распознавать/задавать эти абстрактные математические машины. Приведенные здесь результаты представляют интерес как для теории формальных моделей вычислений, так и для теории формальных языков, поскольку автоматные счетчиковые машины (и соответственно их языки) занимают особое положение в иерархии формализмов в границах от конечных автоматов до машин Тьюринга (счетчиковых машин Минского). Свойства автоматных счетчиковых машин изучаются с привлечением теории правильных квазипорядков и теории вполне структурированных систем переходов, которые оказываются полезными для решения задач анализа семантических свойств различных формальных моделей, являющихся более слабыми по вычислительной мощности (выразительной способности), чем машины Тьюринга. Предназначена для специалистов в области формальных языков и моделей вычислений. Может быть использована студентами старших курсов, магистрантами и аспирантами, специализирующимися в области теоретической информатики и прикладной математики.