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

Lorenzo Clemente
(University of Warsaw)

We 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.

In Laurent Fribourg and Matthias Heizmann: Proceedings 8th International Workshop on Verification and Program Transformation and 7th Workshop on Horn Clauses for Verification and Synthesis (VPT/HCVS 2020), Dublin, Ireland, 25-26th April 2020, Electronic Proceedings in Theoretical Computer Science 320, pp. 29–43.
Published: 7th August 2020.

ArXived at: http://dx.doi.org/10.4204/EPTCS.320.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org