Constructing Semantic Automata for Quantifier Iterations
Sarah McWhirter, Jakub Szymanik

Abstract:
We expand on recent work extending the semantic automata model of quantifier verification to iteration. We demonstrate a simple and
intuitive method to construct a minimal iteration DFA from two DFA recognizing monadic regular quantifier languages and prove that deterministic CFL are also closed under quantifier iteration. We also touch upon the relation between computational results and linguistic
discussion of Frege boundary.