License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.525
URN: urn:nbn:de:0030-drops-32549
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3254/
Go to the corresponding LIPIcs Volume Portal

Straubing, Howard

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

pdf-format:
41.pdf (0.4 MB)

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 =		{10.4230/LIPIcs.CSL.2011.525},
  annote =	{Keywords: automata, finite model theory}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI