Title
Well Quasi Ordering Finite Posets and Formal
Languages
Author
-
Publication
Journal of Combinatorial Theory Ser. B., vol. to appear, 1991
Source
-
Classification
-
not available
Keywords
-
not available
-
-
We show that the set of finite posets is a
well-quasi-ordering with respect to a certain relation
minoreq , called chain minor 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 minoreq has a test in
P}c} whereas c depends on the
property. This test has an easy parallelization with
the same costs. On a parallel machine (CRCW PRAM) it
may be implemented in such a way that it runs in
constant time and needs P}c}
processors.
