Artículo
Becher, V.; Heiber, P.A. "On extending de Bruijn sequences" (2011) Information Processing Letters. 111(18):930-932
Consulte la política de Acceso Abierto del editor
Abstract:
We give a complete proof of the following theorem: Every de Bruijn sequence of order n in at least three symbols can be extended to a de Bruijn sequence of order n+1. Every de Bruijn sequence of order n in two symbols can not be extended to order n+1, but it can be extended to order n+2. © 2011 Elsevier B.V.
Registro:
| Documento: | Artículo |
| Título: | On extending de Bruijn sequences |
| Autor: | Becher, V.; Heiber, P.A. |
| Filiación: | Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, (1428) Buenos Aires, Argentina |
| Palabras clave: | Combinatorial problems; De Bruijn sequences; Graph algorithms; Word problems; Combinatorial problem; DeBruijn sequences; Graph algorithms; Word problem; Theorem proving |
| Año: | 2011 |
| Volumen: | 111 |
| Número: | 18 |
| Página de inicio: | 930 |
| Página de fin: | 932 |
| DOI: | http://dx.doi.org/10.1016/j.ipl.2011.06.013 |
| Título revista: | Information Processing Letters |
| Título revista abreviado: | Inf. Process. Lett. |
| ISSN: | 00200190 |
| CODEN: | IFPLA |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v111_n18_p930_Becher |
Referencias:
- Annexstein, F.S., Generating De Bruijn sequences: An efficient implementation (1997) IEEE Transactions on Computers, 46 (2), pp. 198-200
- Gover De Bruijn, N., A combinatorial problem (1946) Koninklijke Nederlandse Akademie V. Wetenschappen, 49, pp. 758-764. , Indagationes Mathematicae 8 1946 461 467
- Berstel, J., Perrin, D., The origins of combinatorics on words (2007) European Journal of Combinatorics, 28 (3), pp. 996-1022. , DOI 10.1016/j.ejc.2005.07.019, PII S0195669805001629
- Chang, T., Park, B., Kim, Y.H., Song, I., An efficient implementation of the D-homomorphism for generation of de Bruijn sequences (1999) IEEE Transactions on Information Theory, 45 (4), pp. 1280-1283
- Cooper, J., Heitsch, C., The discrepancy of the lex-least de Bruijn sequence (2010) Discrete Mathematics, 310, pp. 1152-1159
- Fredricksen, H., A survey of full length nonlinear shift register cycle algorithms (1982) SIAM Review, 24 (2), pp. 195-221
- Flaxman, A., Harrow, A., Sorkin, G., Strings with maximally many distinct subsequences and substrings (2004) Electronic Journal of Combinatorics, 11. , #R8
- Fleury, M., Deux problèmes de géométrie de situation (1883) Journal de Mathématiques Élémentaires, pp. 257-261
- Good, I.J., Normal recurring decimals (1946) Journal of the London Mathematical Society, 21 (3), pp. 167-169
- Lempel, A., On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers (1970) IEEE Transactions on Computers, 19 C (12), pp. 1204-1209
- Leach, E.B., Regular sequences and frequency distributions (1960) Proceedings of American Mathematical Society, 11, pp. 566-574
- Flye Sainte-Marie, C., Question 48 (1894) Lintermédiaire des Mathématiciens, 1, pp. 107-110
Citas:
---------- APA ----------
Becher, V. & Heiber, P.A. (2011) . On extending de Bruijn sequences. Information Processing Letters, 111(18), 930-932.http://dx.doi.org/10.1016/j.ipl.2011.06.013
---------- CHICAGO ----------
Becher, V., Heiber, P.A. "On extending de Bruijn sequences" . Information Processing Letters 111, no. 18 (2011) : 930-932.http://dx.doi.org/10.1016/j.ipl.2011.06.013
---------- MLA ----------
Becher, V., Heiber, P.A. "On extending de Bruijn sequences" . Information Processing Letters, vol. 111, no. 18, 2011, pp. 930-932.http://dx.doi.org/10.1016/j.ipl.2011.06.013
---------- VANCOUVER ----------
Becher, V., Heiber, P.A. On extending de Bruijn sequences. Inf. Process. Lett. 2011;111(18):930-932.http://dx.doi.org/10.1016/j.ipl.2011.06.013
