文章基本信息

标题：Fragments of First-Order Logic over Infinite Words
本地全文：下载
作者：Volker Diekert ; Manfred Kufleitner
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：3
页码：325-336
DOI：10.4230/LIPIcs.STACS.2009.1818
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic $\mathrm{FO}[<]$ for $\omega$-languages: $\Sigma_2$, $\Delta_2$, $\mathrm{FO}^2 \cap \Sigma_2$ (and by duality $\mathrm{FO}^2 \cap \Pi_2$), and $\mathrm{FO}^2$. These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke (1998) and Boja{\'n}czyk (2008) and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties.
关键词：Infinite words; Regular languages; First-order logic; Automata theory; Semigroups; Topology