Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: VJM banner 

 

Home

 

Recent Issues

Volume 52

1

2

3

 

Volume 51

1

2

3

4

Volume 50

1

2

3

4

Volume 49

1

2

3

4

Volume 48

1

2

3

4

Past Issues

The Journal

Cover

Aims and Scope

Subscription Information

Editorial Board

Instructions for Author

Contact Us

 

 

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