Последовательность Де Брёйна

редактировать

Последовательность де Брёйна для размера алфавита k = 2 и длины подстроки n = 2. В общем, существует множество последовательностей для конкретного n и k, но в этом примере он уникален, от до циклически.

В комбинаторной математике, последовательность де Брейна порядка n в алфавите размера k A - это циклическая последовательность, в которой каждая возможная строка длины n в A встречается ровно один раз как подстрока (т. е. как непрерывная подпоследовательность ). Такая последовательность обозначается B (k, n) и имеет длину k, которая также является количеством различных строк длины n на A. Каждая из этих различных строк, если рассматривать ее как подстроку B (k, n), должны начинаться с другой позиции, потому что подстроки, начинающиеся с одной и той же позиции, не различимы. Следовательно, B (k, n) должно содержать не менее k символов. А поскольку B (k, n) содержит ровно k символов, последовательности Де Брёйна оптимально короткие с точки зрения свойства содержать каждую строку длины n ровно один раз.

Количество различных последовательностей де Брейна B (k, n) равно

(k!) K n - 1 k n. {\ displaystyle {\ dfrac {\ left (k! \ right) ^ {k ^ {n-1}}} {k ^ {n}}}.}

{\ displaystyle {\ dfrac {\ left (k! \ right) ^ {k ^ {n-1}}} {k ^ {n}}}.}

Последовательности названы в честь голландского математика Николаас Говерт де Брюйн, писавший о них в 1946. Как он позже писал, существование последовательностей де Брейна для каждого порядка вместе с указанными выше свойствами было впервые доказано для случая алфавитов с двумя элементами Камиллой Флай Сент-Мари (1894). Обобщение на более крупные алфавиты связано с Татьяной ван Аарден-Эренфест и де Брейн (1951). Автоматы для распознавания этих последовательностей обозначаются как автоматы де Брейна и похожи топологически на некоторые нейронные сети с задержкой по времени.

В большинстве приложений A = {0,1}.

Содержание

1 История
2 Примеры
3 Конструкция
- 3.1 Пример использования графа де Брёйна
- 3.2 Пример использования обратного преобразования Барроуза-Уиллера
- 3.3 Алгоритм
4 Использование
5 f-кратных последовательностей де Брёйна
6 тор Де Брёйна
7 декодирование де Брёйна
8 См. Также
9 Примечания
10 Ссылки
11 Внешние ссылки

История

Самый ранний известный пример последовательности де Брюйна взят из санскритской просодии, где, начиная с работы Пингалы, каждый возможный трехсложный образец длинного и короткого слога является дается имя, например «y» для коротких – длинных – длинных и «m» для длинных – длинных – длинных. Чтобы запомнить эти имена, используется мнемонический образ yamātārājabhānasalagām, в котором каждый трехсложный образец начинается со своего имени: yamātā имеет короткий-длинный-длинный образец, mātārā - длинный-длинный-длинный образец, и так дальше, до «салагама», имеющего структуру короткое-короткое-длинное. Эта мнемоника, эквивалентная последовательности де Брейна на двоичных 3-кортежах, имеет неизвестную древность, но по крайней мере так же стара, как книга Чарльза Филипа Брауна 1869 года по санскритской просодии, в которой она упоминается и рассматривается » древняя строчка, написанная Панини ".

В 1894 году А. де Ривьер в номере французского проблемного журнала L'Intermédiaire des Mathématiciens поднял вопрос о существовании кругового расположения нулей и единиц размера $2 n {\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ , который содержит все $2 n {\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ двоичный последовательности длины $n {\ displaystyle n}$ $n$ . Задача была решена (утвердительно) вместе с подсчетом $2 2 n - 1 - n {\ displaystyle 2 ^ { 2 ^ {n-1} -n}}$ $2 ^ {2 ^ {n-1} -n}$ различных решений, Камилла Флай Сент-Мари в том же году. Об этом в значительной степени забыли, и Мартин (1934) доказал существование таких циклов для общего размера алфавита вместо 2 с алгоритмом их построения. Да, когда в 1944 году Киз Постумус предположил, что количество $2 2 n - 1 - n {\ displaystyle 2 ^ {2 ^ {n-1} -n}}$ $2 ^ {2 ^ {n-1} -n}$ для бинарных последовательностей, де Брейн доказал гипотезу в 1946 году, благодаря чему проблема стала широко известной.

Карл Поппер независимо описывает эти объекты в своей Логике научных открытий (1934), называя их «кратчайшие случайные последовательности».

Примеры

Принимая A = {0, 1}, есть два различных B (2, 3): 00010111 и 11101000, один из которых является обратным или отрицательным другой.
Два из 2048 возможных B (2, 5) в одном алфавите: 00000100011001010011101011011111 и 00000101001000111110111001101011.

Конструкция

График де Брюйна. Каждая четырехзначная последовательность встречается ровно один раз, если пройти через каждое ребро ровно один раз и вернуться в исходную точку (цикл Эйлера). Каждая трехзначная последовательность встречается ровно один раз, если посетить каждую вершину ровно один раз (гамильтонов путь).

Последовательности де Брейна могут быть построены, взяв гамильтонов путь n-мерного граф де Брейна над k символами (или, что то же самое, эйлеров цикл (n - 1) -мерного графа де Брёйна).

Альтернативная конструкция включает в себя объединение вместе, в в лексикографическом порядке, все слова Линдона, длина которых делит n.

Обратное преобразование Барроуза — Уиллера можно использовать для генерации требуемых слов Линдона в лексикографическом порядке.

Последовательности Де Брёйна также могут быть построены с использованием регистров сдвига или с помощью конечных полей.

Пример использования графа де Брёйна

Направленные графы двух B (2,3) de Последовательности Брейна и последовательность B (2,4). В B (2,3). каждая вершина посещается один раз, тогда как в B (2,4) каждое ребро проходит один раз.

Цель: построить последовательность де Брюйна B (2, 4) длины 2 = 16, используя эйлерову (n - 1 = 4 - 1 = 3) Цикл трехмерного графа де Брейна.

Каждое ребро в этом трехмерном графе де Брейна соответствует последовательности из четырех цифр: трех цифр, обозначающих вершину, из которой выходит ребро, за которыми следует цифра, обозначающая ребро. Если пройти по ребру, обозначенному 1 из 000, то получится 001, что указывает на присутствие подпоследовательности 0001 в последовательности де Брюйна. Чтобы пройти каждое ребро ровно один раз, нужно использовать каждую из 16 четырехзначных последовательностей ровно один раз.

Например, предположим, что мы проследуем следующий эйлеров путь через эти вершины:

000, 000, 001, 011, 111, 111, 110, 101, 011,

110, 100, 001, 010, 101, 010, 100, 000.

Это выходные последовательности длины k:

0 0 0 0

_ 0 0 0 1

_ _ 0 0 1 1

Это соответствует следующей последовательности де Брюйна:

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

Восемь вершин появляются в последовательности следующим образом:

{0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 { 1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1...... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1...... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1...

... а затем мы возвращаемся в исходную точку. Каждая из восьми 3-значных последовательностей (соответствующих восьми вершинам) появляется ровно дважды, а каждая из шестнадцати 4-значных последовательностей (соответствующих 16 ребрам) появляется ровно один раз.

Пример использования обратного преобразования Барроуза-Уиллера

Математически обратное преобразование Барроуза-Уиллера для слова w генерирует множественный набор классов эквивалентности, состоящий из строк и их вращений. Каждый из этих классов эквивалентности строк содержит слово Линдона в качестве уникального минимального элемента, поэтому обратное преобразование Барроуза-Уиллера можно рассматривать для генерации набора слов Линдона. Можно показать, что если мы выполним обратное преобразование Барроуза-Уиллера для слова w, состоящего из алфавита размера k, повторяемого k раз (так, чтобы получилось слово той же длины, что и желаемая последовательность де Брейна), то результат будет набором всех слов Линдона, длина которых делит n. Отсюда следует, что расположение этих слов Линдона в лексикографическом порядке даст последовательность де Брейна B (k, n), и что это будет первая последовательность де Брейна в лексикографическом порядке. Следующий метод может использоваться для выполнения обратного преобразования Барроуза-Уиллера с использованием его стандартной перестановки:

Сортировать символы в строке w, получая новую строку w '
Поместите строку w' над строка w и сопоставьте позицию каждой буквы в w 'с ее положением в w, сохраняя порядок. Этот процесс определяет стандартную перестановку.
Запишите эту перестановку в нотации цикла с наименьшей позицией в каждом цикле сначала и циклами, отсортированными в порядке возрастания.
Для каждого цикла, замените каждое число соответствующей буквой из строки w 'в этой позиции.
Каждый цикл теперь стал словом Линдона, и они расположены в лексикографическом порядке, поэтому удаление круглых скобок дает первую последовательность де Брейна.

Например, чтобы построить наименьшую последовательность B (2,4) де Брюйна длиной 2 = 16, повторите алфавит (ab) 8 раз, получив w = abababababababab. Отсортируйте символы в w, получив w '= aaaaaaaabbbbbbbb. Поместите w 'над w, как показано, и сопоставьте каждый элемент в w' с соответствующим элементом в w, нарисовав линию. Пронумеруйте столбцы, как показано, чтобы мы могли прочитать циклы перестановки:

Начиная слева, циклами стандартной перестановки являются: (1) (2 3 5 9) (4 7 13 10) (6 11) ( 8 15 14 12) (16). (Стандартная перестановка )

Затем замена каждого числа соответствующей буквой в w 'из этого столбца дает: (a) (aaab) (aabb) (ab) (abbb) (b).

Это все слова Линдона, длина которых делится на 4, в лексикографическом порядке, поэтому удаление скобок дает B (2,4) = aaaabaabbababbbb.

Алгоритм

Следующий Python Код вычисляет последовательность де Брейна, заданных k и n, на основе алгоритма из Комбинаторной генерации Фрэнка Руски.

def de_bruijn (k, n: int) ->str: " "" последовательность де Брейна для алфавита k и подпоследовательностей длины n. "" "try: # давайте посмотрим, можно ли преобразовать k в целое число; # если да, сделаем наш алфавит списком _ = int (k) алфавит = список ( map (str, range (k))) except (ValueError, TypeError): алфавит = kk = len (k) a = [0] * k * n sequence = def db (t, p): if t>n: if n% p == 0: sequence.extend (a [1: p + 1]) иначе: a [t] = a [t - p] db (t + 1, p) для j в диапазоне (a [t - p] + 1, k): a [t] = j db (t + 1, t) db (1, 1) return "".join (алфавит [ i] для i в последовательности) print (de_bruijn (2, 3)) print (de_bruijn ("abcd", 2))

который печатает

00010111 aabacadbbcbdccdd

Обратите внимание, что эти последовательности понимаются как «завершающие цикл». Например, таким образом первая последовательность содержит 110 и 100.

Использует

одну возможную последовательность B (10, 4). 2530 подстрок читаются сверху вниз, затем слева направо, и их цифры объединяются. Чтобы строка использовалась для подбора кодового замка, добавляются последние три цифры в скобках (000). Строка из 10003 цифр, следовательно, выглядит следующим образом: «0 0001 0002 0003 0004 0005 0006 0007 0008 0009 0011… 79 7988 7989 7998 7999 8 8889 8899 89 8999 9 000» (пробелы добавлены для удобства чтения).

B {10,3} с цифры читаются сверху вниз., затем слева направо; добавление «00» дает. строку для перебора трехзначного кодового замка
0	1	2	3	4	5	6	7	8	9
001
002
003
004
005
006
007
008
009

011
012	112
013	113
014	114
015	115
016	116
017	117
018	118
019	119

021
022	122
023	123	223
024	124	224
025	125	225
026	126	226
027	127	227
028	128	228
029	129	229

031
032	132
033	133	233
034	134	234	334
035	135	235	335
036	136	236	336
037	137	237	337
038	138	238	338
039	139	239	339

041
042	142
043	143	243
044	144	244	344
045	145	245	345	445
046	146	246	346	446
047	147	247	347	447
048	148	248	348	448
049	149	249	349	449

051
052	152
053	153	253
054	154	254	354
055	155	255	355	455
056	156	256	356	456	556
057	157	257	357	457	557
058	158	258	358	458	558
059	159	259	359	459	559

061
062	162
063	163	263
064	164	264	364
065	165	265	365	465
066	166	266	366	466	566
067	167	267	367	467	567	667
068	168	268	368	468	568	668
069	169	269	369	469	569	669

071
072	172
073	173	273
074	174	274	374
075	175	275	375	475
076	176	276	376	476	576
077	177	277	377	477	577	677
078	178	278	378	478	578	678	778
079	179	279	379	479	579	679	779

081
082	182
083	183	283
084	184	284	384
085	185	285	385	485
086	186	286	386	486	586
087	187	287	387	487	587	687
088	188	288	388	488	588	688	788
089	189	289	389	489	589	689	789	889

091
092	192
093	193	293
094	194	294	394
095	195	295	395	495
096	196	296	396	496	596
097	197	297	397	497	597	697
098	198	298	398	498	598	698	798
099	199	299	399	499	599	699	799	899	(00)

Последовательность может быть использована для сокращения атаки грубой силой на PIN -подобный кодовый замок, который не имеет клавиши "ввод" и принимает последние введенные n цифр. Например, цифровой дверной замок с 4-значным кодом (каждая цифра имеет 10 возможных значений от 0 до 9) будет иметь решения B (10, 4) длиной 10000. Следовательно, только не более 10000 + 3 = 10003 (так как решения циклические) необходимо нажатий для открытия замка. Для проверки всех кодов по отдельности потребуется 4 × 10000 = 40000 нажатий.

Символы последовательности де Брюйна, написанные вокруг круглого объекта (например, колеса робота ), могут использоваться для определения его угла путем изучения n последовательные символы, обращенные к фиксированной точке. Эта проблема углового кодирования известна как «проблема вращающегося барабана». Коды Грея могут использоваться как аналогичные механизмы позиционного позиционного кодирования.

Циклы Де Брёйна широко используются в нейробиологических и психологических экспериментах, которые исследуют влияние порядка стимулов на нервные системы, и могут быть специально разработаны для использования с функциональной магнитно-резонансной томографией.

А. Последовательность может использоваться для быстрого поиска индекса младшего значащего бита набора ("крайний правый 1") или самого старшего значащего бита набора ("крайний левый 1") в слове с помощью побитовые операции. Пример возврата индекса младшего разряда из 32-битного целого числа без знака приведен ниже с использованием битовой манипуляции и умножения.

беззнаковое int v; int r; static const int MultiplyDeBruijnBitPosition [32] = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9}; r = MultiplyDeBruijnBitPosition [((uint32_t) ((v -v) * 0x077CB531U))>>27];

Индекс LSB в v сохраняется в r, и если v не имеет установленных битов, операция возвращает 0. Константа 0x077CB531U в выражении представляет собой последовательность B (2, 5) 0000 0111 0111 1100 1011 0101 0011 0001 (для ясности добавлены пробелы).

Пример возврата индекса наиболее значимого набора битов из 32-битного целого числа без знака приведен ниже с использованием манипуляции с битами и умножения.

uint32_t keepHighestBit (uint32_t n) {n | = (n>>1); п | = (п>>2); п | = (п>>4); п | = (п>>8); п | = (п>>16); вернуть n - (n>>1); } uint8_t upperBitIndex (uint32_t b) {статическая константа uint32_t deBruijnMagic = 0x06EB14F9; static const uint8_t deBruijnTable [32] = {0, 1, 16, 2, 29, 17, 3, 22, 30, 20, 18, 11, 13, 4, 7, 23, 31, 15, 28, 21, 19, 10, 12, 6, 14, 27, 9, 5, 26, 8, 25, 24,}; return deBruijnTable [(keepHighestBit (b) * deBruijnMagic)>>27]; }

f-кратная последовательность де Брёйна

f-кратная n-арная последовательность де Брёйна 'является расширением понятия n-арной последовательности де Брёйна, так что последовательность длины $fkn {\ displaystyle fk ^ {n}}$ ${\ displaystyle fk ^ {n}}$ содержит все возможные подпоследовательности длины n ровно f раз. Например, для $n = 2 {\ displaystyle n = 2}$ $n = 2$ циклические последовательности 11100010 и 11101000 представляют собой двойные двоичные последовательности де Брейна. Количество двукратных последовательностей де Брейна, $N n {\ displaystyle N_ {n}}$ $N_n$ для $n = 1 {\ displaystyle n = 1}$ $n = 1$ равно $N 1 = 2 {\ displaystyle N_ {1} = 2}$ ${\ displaystyle N_ {1} = 2}$ , другие известные числа: $N 2 = 5 {\ displaystyle N_ {2} = 5}$ ${\ displaystyle N_ {2} = 5}$ , $N 3 = 72 {\ displaystyle N_ {3} = 72}$ ${\ displaystyle N_ {3} = 72}$ и $N 4 = 43768 {\ displaystyle N_ {4} = 43768}$ ${\ displaystyle N_ {4} = 43768}$ .

тор Де Брейна

A тор де Брейна - тороидальный массив со свойством, что каждая k-арная матрица размером m на n встречается ровно один раз.

Такой шаблон может использоваться для двумерного позиционного кодирования способом, аналогичным описанному выше для вращательного кодирования. Положение можно определить, исследуя матрицу размером m на n, непосредственно расположенную рядом с датчиком, и вычисляя ее положение на торе де Брейна.

Декодирование Де Брёйна

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

См. Также

Примечания

Ссылки

ван Аарденне-Эренфест, Таня ; де Брейн, Николаас Говерт (1951). «Схемы и деревья в ориентированных линейных графах» (PDF). Саймон Стевин. 28: 203–217. MR 0047311. CS1 maint: ref = harv (ссылка )
Aguirre, GK; Mattar, MG; Magis-Weinberg, L. (2011). "циклы де Брюйна" для нейронного декодирования ». NeuroImage. 56 : 1293–1300. CS1 maint: ref = harv (ссылка )
Андерсон, Шон Эрон (1997–2009). «Bit Twiddling Hacks». Стэнфордский университет. Проверено 12 февраля 2009 г. CS1 maint: ref = harv (ссылка )
Берстел, Жан ; Перрен, Доминик (2007). «Истоки комбинаторики слов» (PDF). Европейский журнал комбинаторики. 28(3): 996–1022. doi : 10.1016 / j.ejc.2005.07.019. MR 2300777. CS1 maint: ref = harv (ссылка )
коричневый, CP (1869). Санскритская просодия и объяснение числовых символов. Стр. 28. CS1 maint: ref = harv (link )
de Bruijn, Nicolaas Govert (1946). «Комбинаторная задача» (PDF). Proc. Koninklijke Nederlandse Akademie V. Wetenschappen. 49 : 758–764. MR 0018142, Indagationes Mathematic ae 8: 461–467 CS1 maint: ref = harv (ссылка )
де Брюйн, Николаас Говерт (1975). «Подтверждение приоритета C. Flye Sainte-Marie по подсчету круговых расположений из 2 нулей и единиц, которые показывают каждое слово из n букв ровно один раз» (PDF). T.H.-Отчет 75-WSK-06. Технологический университет Эйндховена. Для цитирования журнала требуется | journal =() CS1 maint: ref = harv (link )
Busch, Philip (2009). «Computing Trailing Zeros HOWTO». Проверено 29 января 2015 г. CS1 maint: ref = harv (ссылка )
Flye Sainte-Marie, Camille (1894). Решение вопроса № 48 ". L'Intermédiaire des Mathématiciens. 1 : 107–110. CS1 maint: ref = harv (link )
Goresky, Mark ; Klapper, Andrew (2012). «8.2.5 Генерация регистров сдвига последовательностей де Брюйна». Алгебраические последовательности регистров сдвига. Cambridge University Press. Pp. 174–175. ISBN 978-1-10701499-2. CS1 maint: ref = harv (ссылка )
Холл, Рэйчел В. (2008). «Математика для поэтов и барабанщиков. " (PDF). Math Horizons. 15 (3): 10–11. doi : 10.1080 / 10724117.2008.11974752. Архивировано из исходный (PDF) от 12 февраля 2012 г. Получено 22 октября 2008 г. CS1 maint: ref = harv (ссылка )
Хиггинс, Питер (ноябрь 2012). «Преобразования Барроуза-Уиллера и слова де Брейна» (PDF). Проверено 11 февраля 2017 г. CS1 maint: ref = harv (ссылка )
Hurlbert, Glenn; Isaak, Garth (1993). «О проблеме тора де Брейна» ( PDF). Journal of Combinatorial Theory. Series A. 64 (1): 50–62. doi : 10.1016 / 0097-3165 (93) 90087-O. MR 1239511. Архивировано из исходного (PDF) 05.09.2006. Проверено 16.07.2006. CS1 maint: ref = harv (ссылка )
Как, Субхаш (2000). «Яматараджабханасалагах интересная комбинаторная сутра» (PDF). Индийский журнал истории науки. 35 (2) : 123–127. Архивировано из оригинального (PDF) от 29.10.2014. CS1 maint: ref = harv (ссылка )
Klein, Andreas (2013). Stream Ciphers. Springer. Стр. 59. ISBN 978-1-44715079-4. CS1 maint: ref = harv (link )
Кнут, Дональд Эрвин (2006). Искусство компьютерного программирования, Часть 4: Создание всех деревьев - История комбинаторного поколения. Эддисон-Уэсли. Стр. 50. ISBN 978-0-321-33570-8. CS1 maint: ref = harv (ссылка )
Фредриксен, Гарольд; Майорана, Джеймс (1978). «Ожерелья из бисера k цветов и k-арных последовательностей де Брюйна». Дискретная математика. 23(3): 207–210. doi : 10.1016 / 0012-365X (78) 90002-X. MR 0523071. CS1 maint: ref = harv (ссылка )
Martin, Monroe H. (1934). «Проблема в расположении» (PDF). Бюллетень Американского математического общества. 40(12): 859–864. doi : 10.1090 / S0002-9904-1934-05988-3. MR 1562989. CS1 maint: ref = harv (link )
Владимир Осипов (2016). "Вейвлет-анализ на Символические последовательности и двумерные последовательности де Брюйна ». Journal of Statistical Physics. 164 (1): 142–165. arXiv : 1601.02097. Bibcode : 2016JSP... 164..142O. doi : 10.1007 / s10955-016-1537-5. ISSN 1572-9613. CS1 maint: ref = harv (ссылка )
Поппер, Карл (2002) [1934]. Логика научных открытий. Routledge. Стр. 294. ISBN 978-0-415-27843-0. CS1 maint: ref = harv (ссылка )
Ральстон, Энтони (1982). «Последовательности де Брейна - модельный пример взаимодействия дискретных математических s и информатика ». Mathematics Magazine. 55(3): 131–143. DOI : 10.2307 / 2690079. JSTOR 2690079. MR 0653429. CS1 maint: ref = harv (link )
Stein, Sherman K. (1963). "Yamátárájabhánasalagám ". Искусственная Вселенная: Введение в Дух математики. Стр. 110–118. CS1 maint: ref = harv (ссылка ) Перепечатано в Wardhaugh, Benjamin, ed.. (2012), A Wealth of Numbers: Anhology of 500 Years of Popular Mathematics Writing, Princeton University Press, pp. 139–144.
Тулиани, Джонатан (2001). "Последовательности де Брейна с эффективными алгоритмами декодирования ». Дискретная математика. 226 (1–3): 313–336. doi : 10.1016 / S0012-365X (00) 00117-5. MR 1802599. CS1 maint: ref = harv (ссылка )
van Lint, JH ; Уилсон, Ричард Майкл (2001). Курс комбинаторики. Cambridge University Press. P. 71. ISBN 978-0-52100601-9. CS1 maint: ref = harv (ссылка )

Внешние ссылки