Some complete -powers of a one-counter language in the difference hierarchy
Organizations: UNIL · Université de Lausanne, Département des opérations, HEC Lausanne, CH-1015, Lausanne, Switzerland · EPFL, Mathematics Section, School of Basic Sciences, CH-1015, Lausanne, Switzerland · IMJ-PRG ·
Abstract
Fix a finite alphabet having at least two letters, and natural numbers . We denote by the class of differences of subsets of the Cantor space in , and by the class of complements of sets in . We prove, for any natural numbers , the existence of a finite alphabet having at least two letters and a finitary language over accepted by a one-counter automaton such that the -power is -complete. We also prove a conditional result for the dual classes : under the assumption that there exists a finitary language accepted by a one-counter automaton, such that its -power is -complete, there would also exist, for any integer , a finitary language accepted by a one-counter automaton, such that its -power is -complete. Finally we add another conditionnal result about Wadge degrees of rational omega powers, which completes the recent results of [FGL26].