The amazing mixed polynomial closure and its applications to two-variable first-order logic
Thomas Place · 2022
Polynomial closure is a standard operator which is applied to a class of regular languages. In this paper, we investigate three restrictions called left (LPol), right (RPol) and mixed polynomial closure (MPol). The first two were known while MPol is new. We look at two decision problems that are defined for every class . Membership takes a regular language as input and asks if it belongs to . Separation takes two regular languages as input and asks if there exists a third language in including the first one and disjoint from the second. We prove that LPol, RPol and MPol preserve the decidability of membership under mild hypotheses on the input class, and the decidability of separation under much stronger hypotheses. We apply these results to natural hierarchies.