Вычислительные возможности односторонних машин Тьюринга с сублогарифмическими ограничениями на память

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