Well-Quasi-Ordering Finite Posets and Formal Languages

Abstract : We show that the set of finite posets is a well-quasi-ordering with respect to a certain relation ≤ called chainminor relation. To prove this we introduce a similar relation on finite formal languages which also has this property. As a consequence we get that every property which is hereditary with respect to ≤ has a polynomial test. This test works also on a parallel machine where it runs in constant time with the same costs.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 1995, 65 (1), pp.111--124
Liste complète des métadonnées

https://hal.inria.fr/inria-00549545
Contributeur : Jens Gustedt <>
Soumis le : mercredi 22 décembre 2010 - 10:45:15
Dernière modification le : samedi 16 décembre 2017 - 07:18:04

Identifiants

  • HAL Id : inria-00549545, version 1

Collections

Citation

Jens Gustedt. Well-Quasi-Ordering Finite Posets and Formal Languages. Journal of Combinatorial Theory, Series B, Elsevier, 1995, 65 (1), pp.111--124. 〈inria-00549545〉

Partager

Métriques

Consultations de la notice

29