Понятие строгой представимости в общей теории исчислений

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