<div class="csl-bib-body">
<div class="csl-entry">Aminof, B., Murano, A., & Rubin, S. (2015). On CTL∗ with Graded Path Modalities. In M. Davis, A. Fehnker, A. McIver, & A. Voronkov (Eds.), <i>Logic for Programming, Artificial Intelligence, and Reasoning : 20th International Conference, LPAR-20 2015, Suva, Fiji, November 24-28, 2015, Proceedings</i>. Fiji Islands. https://doi.org/10.1007/978-3-662-48899-7_20</div>
</div>
The final publication is available via <a href="https://doi.org/10.1007/978-3-662-48899-7_20" target="_blank">https://doi.org/10.1007/978-3-662-48899-7_20</a>.
-
dc.description.abstract
Graded path modalities count the number of paths satisfying a property, and generalize the existential (E) and universal (A) path modalities of CTL∗. The resulting logic is denoted GCTL∗, and is a very powerful logic since (as we show) it is equivalent, over trees, to monadic path logic. We settle the complexity of the satisfiability problem of GCTL∗, i.e., 2ExpTime-Complete, and the complexity of the model checking problem of GCTL∗, i.e., PSpace-Complete. The lower bounds already hold for CTL∗, and so we supply the upper bounds. The significance of this work is two-fold: GCTL∗ is much more expressive than CTL∗ as it adds to it a form of quantitative reasoning, and this is done at no extra cost in computational complexity.
en
dc.description.sponsorship
Austrian Science Funds (RiSE) (FWF)
-
dc.description.sponsorship
Vienna Science and Technology Fund (WWTF)
-
dc.description.sponsorship
European Union's FP7:
-
dc.language
English
-
dc.language.iso
en
-
dc.publisher
Fiji Islands
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.title
On CTL∗ with Graded Path Modalities
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.contributor.affiliation
University of Naples Federico II, Italy
-
dc.contributor.affiliation
University of Naples Federico II, Italy
-
dc.relation.isbn
9783662488997
-
dc.relation.doi
10.1007/978-3-662-48899-7
-
dc.relation.issn
0302-9743
-
dc.relation.grantno
S11403-N23
-
dc.relation.grantno
ICT12-059
-
dc.relation.grantno
600958-SHERPA
-
dc.rights.holder
Springer-Verlag Berlin Heidelberg 2015
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Logic for Programming, Artificial Intelligence, and Reasoning : 20th International Conference, LPAR-20 2015, Suva, Fiji, November 24-28, 2015, Proceedings
-
tuw.container.volume
9450
-
tuw.book.ispartofseries
Lecture Notes in Computer Science
-
tuw.relation.publisher
Springer Berlin
-
tuw.relation.publisherplace
Heidelberg
-
tuw.version
am
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
tuw.publisher.doi
10.1007/978-3-662-48899-7_20
-
dc.identifier.libraryid
AC15148698
-
dc.description.numberOfPages
15
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:3-3808
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.event.name
LPAR: Logic for Programming, Artificial Intelligence, and Reasoning 2015
-
tuw.event.startdate
24-11-2015
-
tuw.event.enddate
28-11-2015
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Suva
-
tuw.event.country
FJ
-
tuw.event.presenter
Aminof, Benjamin
-
item.grantfulltext
open
-
item.fulltext
with Fulltext
-
item.openairetype
conference paper
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-04 - Forschungsbereich Formal Methods in Systems Engineering
