首页    期刊浏览 2024年11月13日 星期三
登录注册

文章基本信息

  • 标题: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
国家哲学社会科学文献中心版权所有