|
Математические заметки, 1988, том 44, выпуск 4, страницы 517–522
(Mi mzm4240)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Последовательность, которая избегает любое полное слово
А. Н. Петров Уральский государственный университет им. А. М. Горького
Аннотация:
Последовательность слов $\{u_i\mid i<\omega\}$ избегает слово $v$, если каждое слово $u_i$ не содержит подслов, полученных из слова $v$ подстановкой слов вместо его букв (при этом одинаковые буквы заменяются одинаковыми словами). Слово $v$ называется полным, если в нем нет букв, входящих ровно один раз, и для любых различных букв $x$, $y$ этого слова, слова $xy$, $yx$ являются его подсловами. Построена бесконечная последовательность слов в алфавите из четырех букв, которая избегает любое полное слово. Показано, что в алфавите из трех букв такой последовательности не существует. Ранее была известна последовательность с указанным свойством в алфавите из двадцати букв (РЖ Мат., 1982, 1А 36). Библиогр. 7 назв.
Поступило: 16.12.1985 Исправленный вариант: 27.05.1887
Образец цитирования:
А. Н. Петров, “Последовательность, которая избегает любое полное слово”, Матем. заметки, 44:4 (1988), 517–522; Math. Notes, 44:4 (1988), 764–767
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm4240 https://www.mathnet.ru/rus/mzm/v44/i4/p517
|
|