Some complete ω-powers of a one-counter language, for any Borel class of finite rank

06/15/2020

∙

by   Olivier Finkel, et al.

∙

0

∙

share

We prove that, for any natural number n ≥ 1, we can find a finite alphabet Σ and a finitary language L over Σ accepted by a one-counter automaton, such that the ω-power L ∞ := w 0 w 1. .. ∈ Σ ω | ∀i ∈ ω w i ∈ L is Π 0 n-complete. We prove a similar result for the class Σ 0 n .