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

On the Complexity of the Universality and Inclusion Problems for Unambiguous Context-Free Grammars

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:38:46Z
dc.abstract.enWe study the computational complexity of universality and inclusion problems for unambiguous finite automata and context-free grammars. We observe that several such problems can be reduced to the universality problem for unambiguous context-free grammars. The latter problem has long been known to be decidable and we propose a PSPACE algorithm that works by reduction to the zeroness problem of recurrence equations with convolution. We are not aware of any non-trivial complexity lower bounds. However, we show that computing the coin-flip measure of an unambiguous context-free language, a quantitative generalisation of universality, is hard for the long-standing open problem SQRTSUM.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorClemente, Lorenzo
dc.date.accessioned2024-01-25T15:46:04Z
dc.date.available2024-01-25T15:46:04Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.description.volume320
dc.identifier.doi10.4204/EPTCS.320.2
dc.identifier.issn2075-2180
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/114788
dc.identifier.weblinkhttp://dx.doi.org/10.4204/eptcs.320.2
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofElectronic Proceedings in Theoretical Computer Science
dc.relation.pages29-43
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleOn the Complexity of the Universality and Inclusion Problems for Unambiguous Context-Free Grammars
dc.typeJournalArticle
dspace.entity.typePublication