Well-Quasi-Ordering Finite Posets and Formal Languages
Gustedt, Jens
HAL, inria-00549545 / Harvested from HAL
Text on HAL
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.
Publié le : 1995-07-05
Classification:  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 
@article{inria-00549545,
     author = {Gustedt, Jens},
     title = {Well-Quasi-Ordering Finite Posets and Formal Languages},
     journal = {HAL},
     volume = {1995},
     number = {0},
     year = {1995},
     language = {en},
     url = {http://dml.mathdoc.fr/item/inria-00549545}
}

Gustedt, Jens. Well-Quasi-Ordering Finite Posets and Formal Languages. HAL, Tome 1995 (1995) no. 0, . http://gdmltest.u-ga.fr/item/inria-00549545/