A note on certain de Bruijn sequences with forbidden subsequences. (English) Zbl 1195.05004
Summary: We consider words over a finite alphabet with certain uniqueness properties (a subsequence of length \(k\) does not occur more than once) and distance properties (at least \(j\) other symbols separate the occurrence of the same symbol). The maximal length of these words is realised by linear de Bruijn sequences with certain forbidden subsequences. We prove the existence of these maximal sequences.
References:
| [1] | Alspach, B.; Liu, G., Path and cycles in matroid base graphs, Graphs and Combinatorics, 5, 1, 207-211 (1989) · Zbl 0692.05017 |
| [2] | Hemminger, R. L.; Beineke, L. W., (Line Graphs and Line Digraphs (1978), Academic Press) · Zbl 0434.05056 |
| [3] | Kawamura, K.; Koku, A. B.; Wilkes, D. M.; Peters II, R. A.; Sekmen, A., Toward egocentric navigation, International Journal of Robotics and Automation, 17, 4, 135-145 (2002) |
| [4] | Moreno, E., De bruijn sequences and de bruijn graphs for a general language, Information Processing Letters, 96, 214-219 (2005) · Zbl 1184.68323 |
| [5] | Nourbakhsh, I. R.; Soto, A.; Bobenage, J.; Grange, S.; Meyer, R.; Lutz, R., An effective mobile robot educator with a full-time job, Artificial Intelligence, 114, 1-2, 95-124 (1999) · Zbl 0939.68864 |
| [6] | Prisner, E., Eulerian iterated line graphs and digraphs, Discrete Mathematics, 236, 1-3, 315-323 (2001) · Zbl 0998.05024 |
| [7] | Ruskey, F.; Sawada, J., (Generating Necklaces and Strings with Forbidden Substrings. Generating Necklaces and Strings with Forbidden Substrings, Lecture Notes in Computer Science, vol. 1858 (2000), Springer: Springer Berlin, Heidelberg), 330-339 · Zbl 0988.68570 |
| [8] | Sammut, C. D., (Robot soccer: Science or Just Fun and Games?. Robot soccer: Science or Just Fun and Games?, Lecture Notes in Computer Science, vol. 2903 (2003), Springer: Springer Berlin, Heidelberg), 12-23 |
| [9] | Tutte, W. T., Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 21 (1984), Cambridge University Press · Zbl 0554.05001 |
| [10] | Zhang, F. J.; Lin, G. N., On the de Bruijn-Good graphs, Acta Mathematica Sinica, 30, 2, 195-205 (1987) · Zbl 0628.05047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
