Weak MSO with the Unbounding Quantifier
Weak MSO with the Unbounding Quantifier
复制标题
具有无界量词的弱 MSO
DOI：
--
复制
发表时间：
2009
影响因子：
0.5
通讯作者：
Mikolaj Bojanczyk
中科院分区：
文献类型：
--
作者：
Mikolaj Bojanczyk
引入了一类新的无限词语言，称为极大正则语言，它是对ω-正则语言的扩充。这个类有两个等价的描述：自动机（一种确定性计数器自动机）和逻辑（带有边界量词的弱一元二阶逻辑）。给出了逻辑和自动机之间的有效转换。
A new class of languages of infinite words is introduced, called the max-regular languages, extending the class of ω-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order logic with a bounding quantifier). Effective translations between the logic and automata are given.