Extending Two-Variable Logic on Trees

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Extending Two-Variable Logic on Trees

Bartosz BednarczykBartosz Bednarczyk,  Witold CharatonikWitold Charatonik,  Emanuel KierońskiEmanuel Kieroński
Bartosz Bednarczyk, Witold Charatonik, Emanuel Kieroński
Extending Two-Variable Logic on Trees
In Valentin Goranko, Mads Dam, eds., Proceedings of 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), volume 82 of Leibniz International Proceedings in Informatics, 11:1--11:20, August 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
  • KurzfassungAbstract
    The finite satisfiability problem for the two-variable fragment of first-order logic interpreted over trees was recently shown to be ExpSpace-complete. We consider two extensions of this logic. We show that adding either additional binary symbols or counting quantifiers to the logic does not affect the complexity of the finite satisfiability problem. However, combining the two extensions and adding both binary symbols and counting quantifiers leads to an explosion of this complexity. We also compare the expressive power of the two-variable fragment over trees with its extension with counting quantifiers. It turns out that the two logics are equally expressive, although counting quantifiers do add expressive power in the restricted case of unordered trees.
  • Weitere Informationen unter:Further Information: Link
  • Forschungsgruppe:Research Group: Computational LogicComputational Logic
@InProceedings{bednarczyk_et_al:LIPIcs:2017:7679,
  author =	{Bartosz Bednarczyk and Witold Charatonik and Emanuel Kieronski},
  title =	{Extending Two-Variable Logic on Trees},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7679},
  URN =		{urn:nbn:de:0030-drops-76794},
  doi =		{10.4230/LIPIcs.CSL.2017.11},
  annote =	{Keywords: two-variable logic, trees, satisfiability, expressivity, counting quantifiers}
}

r Informatik |Editor=Valentin Goranko, Mads Dam |Series=Leibniz International Proceedings in Informatics |Volume=82 }}