Deciding Classes of Regular Languages: The Covering Approach

We investigate the membership problem that one may associate to every class of languages [Formula: see text]. The problem takes a regular language as input and asks whether it belongs to [Formula: see text]. In practice, finding an algorithm provides a deep insight on the class [Formula: see text]. While this problem has a long history, many famous open questions in automata theory are tied to membership. Recently, a breakthrough was made on several of these open questions. This was achieved by considering a more general decision problem than membership: covering. In the paper, we investigate how the new ideas and techniques brought about by the introduction of this problem can be applied to get new insight on earlier results. In particular, we use them to give new proofs for two of the most famous membership results: Schützenberger’s theorem and Simon’s theorem.