Separating Languages over Infinite Words with Product Automata

We study the separation problem for regular languages over infinite words with respect to the Wagner hierarchy. The membership problem is known to be efficiently decidable in this setting. The decision procedure for membership analyses the loop structure of a given automaton. We show that it suffices to analyse the loop structure of the product automaton of two automata in order to decide separability of languages defined by deterministic automata. This leads to an algorithm that determines for two languages the minimal Wagner class that contains a separator and this algorithm runs in polynomial time if the languages are given as deterministic Muller or parity automata. Further, a minimal separator can be constructed in exponential time.

Authors

• Christopher Hugenroth.

Keywords

No keywords are indexed for this paper.