Исследуется ли следующее расширение конечных автоматов?

Рассмотрим конечный автомат как обычно, но при каждом переходе он также может обновлять целочисленный счетчик, добавляя или вычитая число. Скажем, переходная функция вида перемещается в новое состояние и добавляет в счетчик, где (так что может быть положительным , отрицательный или ноль).$\delta(q,a) = (p,k)$$p$$k$$k \in \mathbb{Z}$$k$

Строка принимается, если конечное состояние и значение счетчика находятся в , где - конечный набор пар состояний и значений счетчика.$F$$F$

Эта модель известна? Я не мог найти ссылку на это конкретное расширение.

Если предположить, что может быть любым целым числом, то это можно формализовать как слепой автомат с одним счетчиком . Обычно эти автоматы принимают в конечном состоянии, когда его счетчик равен нулю, но мы можем легко смоделировать ваш тип принятия, если вы разрешите переходы (которые не потребляют ввод). Если я не ошибаюсь, как в случае конечных автоматов, можно избавиться от , но это нетривиальный результат.ϵ $k$$\epsilon$$\epsilon$

Существует несколько типов автоматов с одним счетчиком. В наиболее общем виде им разрешается проверять, равно ли значение счетчика нулю. Языки, которые они принимают, являются строгим подмножеством языков без контекста.

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

Эта модель является вариантом взвешенных автоматов, которые широко изучаются (хотя о них много открытых вопросов). Вы можете начать здесь: Справочник взвешенных автоматов .

Обратите внимание, что иногда их называют «автоматами расстояния» (хотя это становится все менее распространенным).