← All problems
Unverified
Fine-grained complexity of omega-automata inclusion
The inclusion problem asks whether the language of an automaton is included in that of an automaton . If the automaton is deterministic, this problem can be solved in almost quadratic time by a product construction, and this bound is optimal: a algorithm would contradict ETH (Wehar 2016). For automata over infinite words, the problem is still in PTIME (in NL in fact), but its exact complexity is unknown. Find upper and lower bounds on such that the inclusion of deterministic parity automata can(not) be checked in time .
