|
|
|
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.
|
|
|
|
Established
by Vietnam Academy of Science and Technology & Vietnam Mathematical
Society
Published
by Springer since January 2013
|
|
