← All problems
Unverified

Fine-grained complexity of omega-automata inclusion

The inclusion problem asks whether the language of an automaton AA is included in that of an automaton BB. If the automaton BB is deterministic, this problem can be solved in almost quadratic time by a product construction, and this bound is optimal: a o(n2)o(n^2) 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. ∗∗Goal:∗∗**Goal:** Find upper and lower bounds on kk such that the inclusion of deterministic parity automata can(not) be checked in time O(nk)O(n^k).

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu