Quantifier Alternation for Infinite Words
Quantifier Alternation for Infinite Words
复制标题
无限词的量词交替
DOI：
10.1007/978-3-662-49630-5_14
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Zeitoun
中科院分区：
文献类型：
--
作者：
Théo Pierron;Thomas Place;M. Zeitoun
We investigate the expressive power of the quantifier alternation hierarchy of first-order logic over words. This hierarchy includes the classes \(\varSigma _{{i}}\) (sentences having at most i blocks of quantifiers starting with an \(\exists \)) and \(\mathcal {B}\varSigma _{{i}}\) (Boolean combinations of \(\varSigma _{{i}}\) sentences). So far, this expressive power has been effectively characterized for the lower levels only. Recently, a breakthrough was made over finite words, and decidable characterizations were obtained for \(\mathcal {B}\varSigma _{2}\) and \(\varSigma _{3}\), by relying on a decision problem called separation, and solving it for \(\varSigma _{2}\).
We investigate the expressive power of the quantifier alternation hierarchy of first-order logic over words. This hierarchy includes the classes \(\varSigma _{{i}}\) (sentences having at most i blocks of quantifiers starting with an \(\exists \)) and \(\mathcal {B}\varSigma _{{i}}\) (Boolean combinations of \(\varSigma _{{i}}\) sentences). So far, this expressive power has been effectively characterized for the lower levels only. Recently, a breakthrough was made over finite words, and decidable characterizations were obtained for \(\mathcal {B}\varSigma _{2}\) and \(\varSigma _{3}\), by relying on a decision problem called separation, and solving it for \(\varSigma _{2}\).
无限单词上的量词交替层次结构的第二级
影响因子：
0.5
作者：
M. Kufleitner;T. Walter
通讯作者：
T. Walter