{'fraction_non_alphanumeric': 0.028685790527018012, 'fraction_numerical': 0.00133422281521014, 'mean_word_length': 4.597014925373134, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithmic Aspects of Ordered Structures

In this work we relate the theory of quasi-orders to the theory of algorithms over some combinatorial objects. First we develope the theory of well-quasi-orderings, wqo's, and relate it to the theory of worst-case complexity. Then we give a general 0-1-law for hereditary properties that has implications for average-case complexity. This result on average-case complexity is applied to the class of finite graphs equipped with the induced subgraph relation. We obtain that a wide class of problems, including e.g. perfectness, has average constant time algorithms. Then we show, by extending a result of Damaschke on cographs, that the classes of finite orders resp. graphs with bounded decomposition diameter form wqo's with respect to the induced suborder resp. induced subgraph relation. This leads to linear time algorithms for the recognition of any hereditary property on these objects. Our main result is then that the set of finite posets is a wqo with respect to a certain relation l, called chain minor relation. To prove this we introduce a similar relation on finite formal languages that also has this property. As a consequence we obtain that every property which is hereditary with respect to l has a test in O(|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 O(|P|c) processors.