Huschenbett, Martin ;
Kufleitner, Manfred
Ehrenfeucht-Fraïssé Games on Omega-Terms
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].
BibTeX - Entry
@InProceedings{huschenbett_et_al:LIPIcs:2014:4472,
author = {Martin Huschenbett and Manfred Kufleitner},
title = {{Ehrenfeucht-Fraiss{\'e} Games on Omega-Terms}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {374--385},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4472},
URN = {urn:nbn:de:0030-drops-44729},
doi = {10.4230/LIPIcs.STACS.2014.374},
annote = {Keywords: regular language, first-order logic, finite monoid, Ehrenfeucht-Fraiss{\'e} games, pseudoidentity}
}
Keywords: |
|
regular language, first-order logic, finite monoid, Ehrenfeucht-Fraïssé games, pseudoidentity |
Seminar: |
|
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
|
Issue date: |
|
2014 |
Date of publication: |
|
05.03.2014 |
05.03.2014