2020/06/09 by Lorenzo Clemente, Clemente, Lorenzo · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2006.05275
full technical report of a paper to appear in VPT 2020
openalex publication_date 2020/06/09 · arxiv created 2020/06/11 · arxiv updated 2020/06/12 · openalex created_date 2020/06/19 · openalex updated_date 2026/07/28
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.