{'fraction_non_alphanumeric': 0.027739251040221916, 'fraction_numerical': 0.0, 'mean_word_length': 5.170940170940171, '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}}
Monadic logic and automata: recent developments

This tutorial surveys selected recent results on the connection between monadic second-order logic and finite automata. As a unifying idea, the role of automata as normal forms of monadic formulas is pursued. In the first part we start from an automata-theoretic interpretation of existential monadic second-order formulas and in this framework explain the monadic quantifier alternation hierarchy over finite graphs. In the second part, infinite models, in particular /spl omega/-words, are considered. We analyze the logical significance of central constructions in /spl omega/-automata theory and sketch new proofs of decidability results in monadic second-order logic.