带有图循环的关系Kleene代数的等式理论的PSPACE完全性

本文确立了带有图循环的关系Kleene代数的等式理论的PSPACE完全性，这是理论计算机科学中的一个重要成果。它将此结果扩展到包括top、tests、converse和nominals等其他运算符。引入循环自动机以及简化为双向交替字符串自动机的语言包含问题是关键贡献。本文还区分了在Kleene代数with tests (KAT)中使用domain与antidomain时的复杂性，突出了这些代数系统的细微差别。

• •带有图循环的关系Kleene代数的等式理论是PSPACE完全的。
• •即使扩展了top、tests、converse和nominals，这种PSPACE完全性仍然成立。
• •本文引入了循环自动机，并使用它们将问题简化为双向交替字符串自动机的语言包含问题。
• •对于带有domain的KAT（PSPACE完全）和带有antidomain的KAT（ExpTime完全），复杂性有所不同。