文章基本信息

标题：Algebraic Characterization of FO for Scattered Linear Orderings
本地全文：下载
作者：Alexis B{\`e}s ; Olivier Carton
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：12
页码：67-81
DOI：10.4230/LIPIcs.CSL.2011.67
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that for the class of sets of words indexed by countable scattered linear orderings, there is an equivalence between definability in first-order logic, star-free expressions with marked product, and recognizability by finite aperiodic semigroups which satisfy some additional equation.
关键词：linear orderings; first-order logic; semigroups; rational sets