2026-08-11T17:50:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8375 2024-03-06T10:42:01Z ddc:004 open_access

The Complexity of the Diagonal Problem for Recursion Schemes Parys, Pawel diagonal problem higher-order recursion schemes intersection types downward closure We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We establish the complexity of the diagonal problem for schemes: given a set of letters A and a scheme G, is it the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. We prove that this problem is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Parys 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.45 urn:nbn:de:0030-drops-83757 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.45 eng https://creativecommons.org/licenses/by/3.0/legalcode