文章基本信息

标题：Size-Preserving Translations from Order-(n+1) Word Grammars to Order-n Tree Grammars
本地全文：下载
作者：Kazuyuki Asada ; Naoki Kobayashi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：167
页码：22:1-22:22
DOI：10.4230/LIPIcs.FSCD.2020.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：higher-order grammar; word language; tree language; complexity