一句话:为高阶模型检测构造笛卡尔闭范畴,并借助Büchi自动机的有限抽象格实现忠实抽象与不动点计算。
本文围绕标题所示的高阶模型检测笛卡尔闭范畴展开,研究其范畴论与抽象语义基础。摘要回顾了先前从给定Büchi自动机构造抽象格的方法:该抽象格是有限的,并与给定字母表上有限字和无限字语言构成的格之间存在Galois插入。该抽象对于自动机的接受性保持忠实,即可通过抽象层信息判断原自动机是否接受。进一步,最小不动点和ω迭代可以在抽象格层面计算,而最大不动点一般不具此性质。这些结果为在高阶模型检测中利用有限抽象进行不动点推理提供了语义与代数基础。
In previous work we have described the construction of an abstract lattice from a given Büchi automaton. The abstract lattice is finite and has the following key properties. (i) There is a Galois insertion between it and the lattice of languages of finite and infinite words over a given alphabet. (ii) The abstraction is faithful with respect to acceptance by the automaton. (iii) Least fixpoints and ω-iterations (but not in general greatest fixpoints) can be computed on the level of the abstract lattice.