RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Математического института имени В. А. Стеклова // Архив

Тр. МИАН СССР, 1967, том 93, страницы 43–49 (Mi tm2825)

Общая теория алгорифмов и исчислений

Представление перечислимых множеств локальными исчислениями

С. Ю. Маслов


Аннотация: Изучаются возможности представления множеств локальными исчислениями специальных типов. Например, каждое перечислимое множество $\mathfrak M$ слов в алфавите $A$ удается представить узколокальным исчислением (для каждой схемы узколокального исчисления изменяемый отрезок слова содержит не более двух букв), не содержащим краевых схем, обратимым узколокальным исчислением, обратимым локальным исчислением в однобуквенном расширении алфавита $A$. Для случая, когда $A$ содержит не менее двух букв, $\mathfrak M$ можно представить в однобуквенном расширении алфавита $A$ узколокальным вполне каноническим исчислением с главным алфавитом $A$ и можно представить узколокальным вполне каноническим исчислением (вполне канонические исчисления – это исчисления, у которых значения схемных переменных обязательно являются словами в главном алфавите).
Библ. – 2 назв.

УДК: 51.01+518.5



Реферативные базы данных:


© МИАН, 2024