文章基本信息

标题：Ehrenfeucht-Fraïssé Games on Omega-Terms
本地全文：下载
作者：Martin Huschenbett ; Manfred Kufleitner
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：374-385
DOI：10.4230/LIPIcs.STACS.2014.374
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Fragments of first-order logic over words can often be characterized in terms of finite monoids or finite semigroups. Usually these algebraic descriptions yield decidability of the question whether a given regular language is definable in a particular fragment. An effective algebraic characterization can be obtained from identities of so-called omega-terms. In order to show that a given fragment satisfies some identity of omega-terms, one can use Ehrenfeucht-Fraisse games on word instances of the omega-terms. The resulting proofs often require a significant amount of book-keeping with respect to the constants involved. In this paper we introduce Ehrenfeucht-Fraisse games on omega-terms. To this end we assign a labeled linear order to every omega-term. Our main theorem shows that a given fragment satisfies some identity of omega-terms if and only if Duplicator has a winning strategy for the game on the resulting linear orders. This allows to avoid the book-keeping. As an application of our main result, we show that one can decide in exponential time whether all aperiodic monoids satisfy some given identity of omega-terms, thereby improving a result of [McCammond, Int. J. Algebra Comput. 2001].
关键词：regular language; first-order logic; finite monoid; Ehrenfeucht-Fraiss{\'e