一句话：综述正则语言的差分层级，介绍Hausdorff经典技术，并给出shuffle理想、强循环正则语言与群语言多项式闭包的可判定性结果。
该综述研究正则语言的差分层级（difference hierarchies），这一概念由Hausdorff提出并在描述集合论中具有重要作用。文章前几节系统整理差分层级的标准技术，主要源自Hausdorff，包括层级构造与基本性质。随后利用这些技术，针对三类正则语言类——shuffle理想、强循环正则语言以及群语言的多项式闭包——建立相应差分层级的可判定性结果。评估以数学证明与可判定性分析为主，不涉及实现或实验。整体为后续研究正则语言的表达力、代数性质与逻辑刻画提供统一框架和工具。
Difference hierarchies were originally introduced by Hausdorff and they play an important role in descriptive set theory. In this survey paper, we study difference hierarchies of regular languages. The first sections describe standard techniques on difference hierarchies, mostly due to Hausdorff. We illustrate these techniques by giving decidability results on the difference hierarchies based on shuffle ideals, strongly cyclic regular languages and the polynomial closure of group languages.
@article{paperbot417,
title = {A survey on difference hierarchies of regular languages},
author = {Olivier Carton and Dominique Perrin and Jean-Éric Pin},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 1},
year = {2018},
doi = {10.23638/lmcs-14(1:24)2018}
}