Ehrenfeucht-Fraïssé Games on Omega-Terms

Authors Martin Huschenbett, Manfred Kufleitner



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.374.pdf
  • Filesize: 0.67 MB
  • 12 pages

Document Identifiers

Author Details

Martin Huschenbett
Manfred Kufleitner

Cite AsGet BibTex

Martin Huschenbett and Manfred Kufleitner. Ehrenfeucht-Fraïssé Games on Omega-Terms. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 374-385, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.374

Abstract

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].
Keywords
  • regular language
  • first-order logic
  • finite monoid
  • Ehrenfeucht-Fraïssé games
  • pseudoidentity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail