1 Search Results for "Ferrarotti, Flavio"

Expressivity Within Second-Order Transitive-Closure Logic

Authors: Flavio Ferrarotti, Jan Van den Bussche, and Jonni Virtema

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Second-order transitive-closure logic, SO(TC), is an expressive declarative language that captures the complexity class PSPACE. Already its monadic fragment, MSO(TC), allows the expression of various NP-hard and even PSPACE-hard problems in a natural and elegant manner. As SO(TC) offers an attractive framework for expressing properties in terms of declaratively specified computations, it is interesting to understand the expressivity of different features of the language. This paper focuses on the fragment MSO(TC), as well on the purely existential fragment SO(2TC)(exists); in 2TC, the TC operator binds only tuples of relation variables. We establish that, with respect to expressive power, SO(2TC)(exists) collapses to existential first-order logic. In addition we study the relationship of MSO(TC) to an extension of MSO(TC) with counting features (CMSO(TC)) as well as to order-invariant MSO. We show that the expressive powers of CMSO(TC) and MSO(TC) coincide. Moreover we establish that, over unary vocabularies, MSO(TC) strictly subsumes order-invariant MSO.

Cite as

Flavio Ferrarotti, Jan Van den Bussche, and Jonni Virtema. Expressivity Within Second-Order Transitive-Closure Logic. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 22:1-22:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

  author =	{Ferrarotti, Flavio and Van den Bussche, Jan and Virtema, Jonni},
  title =	{{Expressivity Within Second-Order Transitive-Closure Logic}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.22},
  URN =		{urn:nbn:de:0030-drops-96896},
  doi =		{10.4230/LIPIcs.CSL.2018.22},
  annote =	{Keywords: Expressive power, Higher order logics, Descriptive complexity}
  • Refine by Author
  • 1 Ferrarotti, Flavio
  • 1 Van den Bussche, Jan
  • 1 Virtema, Jonni

  • Refine by Classification
  • 1 Theory of computation → Finite Model Theory

  • Refine by Keyword
  • 1 Descriptive complexity
  • 1 Expressive power
  • 1 Higher order logics

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail