Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Straubing, Howard http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-32549
URL:

Algebraic Characterization of the Alternation Hierarchy in FO^2[<] on Finite Words

pdf-format:


Abstract

We give an algebraic characterization of the quantifier alternation hierarchy in first-order two-variable logic on finite words. As a result, we obtain a new proof that this hierarchy is strict. We also show that the first two levels of the hierarchy have decidable membership problems, and conjecture an algebraic decision procedure for the other levels.

BibTeX - Entry

@InProceedings{straubing:LIPIcs:2011:3254,
  author =	{Howard Straubing},
  title =	{{Algebraic Characterization of the Alternation Hierarchy in FO^2[<] on Finite Words}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{525--537},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Marc Bezem},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3254},
  URN =		{urn:nbn:de:0030-drops-32549},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.CSL.2011.525},
  annote =	{Keywords: automata, finite model theory}
}

Keywords: automata, finite model theory
Seminar: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue date: 2011
Date of publication: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI