2026-07-25T02:44:16Z https://drops.dagstuhl.de/oai

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

Size-Preserving Translations from Order-(n+1) Word Grammars to Order-n Tree Grammars Asada, Kazuyuki Kobayashi, Naoki higher-order grammar word language tree language complexity Higher-order grammars have recently been studied actively in the context of automated verification of higher-order programs. Asada and Kobayashi have previously shown that, for any order-(n+1) word grammar, there exists an order-n grammar whose frontier language coincides with the language generated by the word grammar. Their translation, however, blows up the size of the grammar, which inhibited complexity-preserving reductions from decision problems on word grammars to those on tree grammars. In this paper, we present a new translation from order-(n+1) word grammars to order-n tree grammars that is size-preserving in the sense that the size of the output tree grammar is polynomial in the size of an input tree grammar. The new translation and its correctness proof are arguably much simpler than the previous translation and proof. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazuyuki Asada and Naoki Kobayashi 2020 Is Part Of LIPIcs, Volume 167, 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSCD.2020.22 urn:nbn:de:0030-drops-123440 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.22 eng https://creativecommons.org/licenses/by/3.0/legalcode