论文标题
确定性欧米茄受体的包含和等效性的多项式时间算法
Polynomial time algorithms for inclusion and equivalence of deterministic omega acceptors
论文作者
论文摘要
确定性平价受体（DPA）或确定性muller受体（DMA）认可的欧米茄语言类正是常规的欧米茄语言。包含问题是：给定两个受体A1和A2，确定A1识别的语言是否是A2识别的语言的子集，如果没有，则返回最终由A1接受的最终定期的Omega单词，而不是A2。我们描述了为两个DPA和两个DMA解决此问题的多项式时间算法。推论包括解决DPA和DMA的等效问题的多项式时间算法，以及确定性Buechi和Cobuechi受体的包含和等效问题。
The class of omega languages recognized by deterministic parity acceptors (DPAs) or deterministic Muller acceptors (DMAs) is exactly the regular omega languages. The inclusion problem is the following: given two acceptors A1 and A2, determine whether the language recognized by A1 is a subset of the language recognized by A2, and if not, return an ultimately periodic omega word accepted by A1 but not A2. We describe polynomial time algorithms to solve this problem for two DPAs and for two DMAs. Corollaries include polynomial time algorithms to solve the equivalence problem for DPAs and DMAs, and also the inclusion and equivalence problems for deterministic Buechi and coBuechi acceptors.
