Recent Issues Volume 37 1 2 3 4 Volume 36 1 2 3 4 Volume 35 1 2 3 4 Volume 34 1 2 3 4 Volume 33 1 2 3 4 Past Issues The Journal Cover Aims and Scope Subscription Information Editorial Board Instructions for Author Contact Us Related Links

Vietnam Journal of Mathematics 34:4(2006) 459-472  Generating of Minimal Unavoidable Sets Phan Trung Huy and Nguyen Thi Thanh Huyen Abstract.  In this paper we investigate several transformations on unavoidable sets which preserve the minimality of such sets. The main result confirms that any minimal unavoidable set over an alphabet $A$ can be obtained from $A$, regarded as the initial manimal unavoidable set, by finitely many applications of such transformations. As a consequence, a procedure to generate all possible minimal unavoidable sets over $A$ is proposed. This allows in particular to generate easily counter-examples for both the Ehrenfeucht's conjecture and Haussler's one on unavoidable sets.   2000 Mathematics Subject Classification: 68R15, 68S05. Keywords: Unavoidable set, transformation, reduced, minimal, generating, conjecture.

Vietnam Academy of Science and Technology & Vietnamese Mathematical Society © Copyright 2009 Vietnam Journal of Mathematics. All rights reserved.