RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 1988, том 44, выпуск 4, страницы 517–522 (Mi mzm4240)

Эта публикация цитируется в 2 статьях

Последовательность, которая избегает любое полное слово

А. Н. Петров

Уральский государственный университет им. А. М. Горького

Аннотация: Последовательность слов $\{u_i\mid i<\omega\}$ избегает слово $v$, если каждое слово $u_i$ не содержит подслов, полученных из слова $v$ подстановкой слов вместо его букв (при этом одинаковые буквы заменяются одинаковыми словами). Слово $v$ называется полным, если в нем нет букв, входящих ровно один раз, и для любых различных букв $x$, $y$ этого слова, слова $xy$, $yx$ являются его подсловами. Построена бесконечная последовательность слов в алфавите из четырех букв, которая избегает любое полное слово. Показано, что в алфавите из трех букв такой последовательности не существует. Ранее была известна последовательность с указанным свойством в алфавите из двадцати букв (РЖ Мат., 1982, 1А 36). Библиогр. 7 назв.

УДК: 512.53

Поступило: 16.12.1985
Исправленный вариант: 27.05.1887


 Англоязычная версия: Mathematical Notes, 1988, 44:4, 764–767

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


© МИАН, 2024