2026-07-22T07:05:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4472 2024-03-06T10:35:05Z ddc:004 open_access

Ehrenfeucht-Fraïssé Games on Omega-Terms Huschenbett, Martin Kufleitner, Manfred regular language first-order logic finite monoid Ehrenfeucht-Fraïssé games pseudoidentity 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Huschenbett and Manfred Kufleitner 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.374 urn:nbn:de:0030-drops-44729 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.374 eng https://creativecommons.org/licenses/by/3.0/legalcode