Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Computing Bisimulation-Based Comparisons

Uproszczony widok
dc.abstract.enWe provide the first algorithm with a polynomial time complexity, O((m + n)^2 n^2), for computing the largest bisimulation-based auto-comparison of a labeled graph in the setting with counting successors, where m is the number of edges and n is the number of vertices. This setting is like the case with graded modalities in modal logics and qualified number restrictions in description logics. Furthermore, by using the idea of Henzinger et al. for computing simulations, we give an efficient algorithm, with complexity O((m + n)n), for computing the largest bisimulation-based auto-comparison and the directed similarity relation of a labeled graph in the setting without counting successors. We also adapt our former algorithm for computing the simulation pre-order of a labeled graph in the setting with counting successors.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorNguyen, Anh Linh
dc.date.accessioned2024-01-24T19:52:48Z
dc.date.available2024-01-24T19:52:48Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.description.number4
dc.description.volume157
dc.identifier.doi10.3233/FI-2018-1634
dc.identifier.issn0169-2968
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/103486
dc.identifier.weblinkhttps://content.iospress.com/articles/fundamenta-informaticae/fi1634
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofFundamenta Informaticae
dc.relation.pages385-401
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleComputing Bisimulation-Based Comparisons
dc.typeJournalArticle
dspace.entity.typePublication