Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/27342
Title: | Expressivity Within Second-Order Transitive-Closure Logic | Authors: | Ferrarotti, Flavio VAN DEN BUSSCHE, Jan VIRTEMA, Jonni |
Issue Date: | 2018 | Publisher: | Schloss Dagstuhl -- Leibniz-Zentrum für Informatik | Source: | Ghica, Dan; Jung, Achim (Ed.). 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), Schloss Dagstuhl -- Leibniz-Zentrum für Informatik,p. 1-18 (Art N° 22) | Series/Report: | Leibniz International Proceedings in Informatics (LIPIcs) | Abstract: | 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)(∃); in 2TC, the TC operator binds only tuples of relation variables. We establish that, with respect to expressive power, SO(2TC)(∃) 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. | Keywords: | expressive power; higher order logics; descriptive complexity | Document URI: | http://hdl.handle.net/1942/27342 | ISBN: | 9783959770880 | DOI: | 10.4230/LIPIcs.CSL.2018.22 | Rights: | © Flavio Ferrarotti, Jan Van den Bussche, and Jonni Virtema; licensed under Creative Commons License CC-BY | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-CSL-2018-22.pdf | Published version | 499.06 kB | Adobe PDF | View/Open |
Page view(s)
20
checked on Sep 5, 2022
Download(s)
4
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.