We revisit the membership problem for subclasses of rational relations over finite and infinite words: Given a relation R in a class C_2, does R belong to a smaller class C_1? The subclasses of rational relations that we consider are formed by the deterministic rational relations, synchronous (also called automatic or regular) relations, and recognizable relations. For almost all versions of the membership problem, determining the precise complexity or even decidability has remained an open problem for almost two decades. In this paper, we provide improved complexity and new decidability results. (i) Testing whether a synchronous relation over infinite words is recognizable is NL-complete (PSPACE-complete) if the relation is given by a deterministic (nondeterministic) omega-automaton. This fully settles the complexity of this recognizability problem, matching the complexity of the same problem over finite words. (ii) Testing whether a deterministic rational binary relation is recognizable is decidable in polynomial time, which improves a previously known double exponential time upper bound. For relations of higher arity, we present a randomized exponential time algorithm. (iii) We provide the first algorithm to decide whether a deterministic rational relation is synchronous. For binary relations the algorithm even runs in polynomial time.
翻译:我们重新审视有限和无限字上的有理关系子类的成员问题:给定类别C_2中的一个关系R,R是否属于较小的类别C_1?我们考虑的有理关系子类是由确定有限自动机,同步(也称为自动或常规)关系和可识别关系形成的。对于几乎所有成员问题的版本,几乎已经有近二十年时间,确定复杂性甚至可决定性仍然是一个悬而未决的问题。在本文中,我们提供了改进的复杂度和新的可决定性结果。 (i) 对于用确定的(非确定的)无限自动机给出的同步关系,测试它是否可识别是NL完全的(PSPACE完全的)。这个收敛性问题的复杂度已经得到充分解决,与相同问题的有限字版本的复杂度相匹配。 (ii) 测试确定的有理二元关系是否可识别是可在多项式时间内决定的,这正在改善先前已知的双重指数时间上限。对于更高阶的关系,我们提供了一个随机指数时间算法。 (iii) 我们提供了第一个算法来决定一个确定的有理关系是否同步。对于二元关系,该算法甚至可以在多项式时间内运行。