DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2014.374

Ehrenfeucht-Fraïssé Games on Omega-Terms

Authors: Martin Huschenbett and Manfred Kufleitner

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

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].

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{huschenbett_et_al:LIPIcs.STACS.2014.374,
  author =	{Huschenbett, Martin and Kufleitner, Manfred},
  title =	{{Ehrenfeucht-Fra\"{i}ss\'{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 =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.374},
  URN =		{urn:nbn:de:0030-drops-44729},
  doi =		{10.4230/LIPIcs.STACS.2014.374},
  annote =	{Keywords: regular language, first-order logic, finite monoid, Ehrenfeucht-Fra\"{i}ss\'{e} games, pseudoidentity}
}

Document

DOI: 10.4230/LIPIcs.STACS.2013.586

The Rank of Tree-Automatic Linear Orderings

Authors: Martin Huschenbett

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract

A tree-automatic structure is a structure whose domain can be encoded by a regular tree language such that each relation is recognisable by a finite automaton processing tuples of trees synchronously. The finite condensation rank (FC-rank) of a linear ordering measures how far it is away from being dense. We prove that the FC-rank of every tree-automatic linear ordering is below omega^omega. This generalises Delhommé's result that each tree-automatic ordinal is less than omega^omega^omega. Furthermore, we show an analogue for tree-automatic linear orderings where the branching complexity of the trees involved is bounded.

Cite as

Martin Huschenbett. The Rank of Tree-Automatic Linear Orderings. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 586-597, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{huschenbett:LIPIcs.STACS.2013.586,
  author =	{Huschenbett, Martin},
  title =	{{The Rank of Tree-Automatic Linear Orderings}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{586--597},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.586},
  URN =		{urn:nbn:de:0030-drops-39672},
  doi =		{10.4230/LIPIcs.STACS.2013.586},
  annote =	{Keywords: tree-automatic structures, linear orderings, finite condensation rank, computable model theory}
}

Search Results

Documents authored by Huschenbett, Martin

Ehrenfeucht-Fraïssé Games on Omega-Terms

Abstract

Cite as

The Rank of Tree-Automatic Linear Orderings

Abstract

Cite as

Thanks for your feedback!

Could not send message