Context-Free Tree Grammars are as Powerful as Context-Free Jungle Grammars

被引：0
|
作者：
Drewes, Frank [1 ]
Engelfriett, Joost [2 ]
机构：
[1] Umea Univ, Dept Comp Sci, S-90187 Umea, Sweden
[2] Leiden Univ, Leiden Inst Adv Comp Sci, NL-2300 RA Leiden, Netherlands
来源：
ACTA CYBERNETICA | 2015年 / 22卷 / 02期
关键词：
context-free tree grammar; jungle; delegation network;
D O I：
10.14232/actacyb.22.2.2015.9
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Jungles generalize trees by sharing subtrees and allowing garbage. It is shown that IO context-free tree grammars generate the same jungle languages as context-free jungle grammars. Also, they define the same subsets of any algebra.
引用
收藏
页码：373 / 392
页数：20
相关论文
共 50 条
  • [1] Generalized context-free grammars and multiple context-free grammars
    Kasami, Tadao
    Seki, Hiroyuki
    Fujii, Mamoru
    Systems and Computers in Japan, 1989, 20 (07): : 43 - 52
  • [2] Tree generating context-free grammars and regular tree grammars are equivalent
    Koszo, David
    ANNALES MATHEMATICAE ET INFORMATICAE, 2022, 56 : 58 - 70
  • [3] REDUCTION OF CONTEXT-FREE GRAMMARS
    TANIGUCHI, K
    KASAMI, T
    ELECTRONICS & COMMUNICATIONS IN JAPAN, 1969, 52 (12): : 204 - +
  • [4] CONTEXT-FREE GRAMMARS WITH MEMORY
    MORIYA, E
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1992, E75D (06) : 847 - 851
  • [5] On translating context-free grammars into Lambek grammars
    S. L. Kuznetsov
    Proceedings of the Steklov Institute of Mathematics, 2015, 290 : 63 - 69
  • [6] Context-Free Categorical Grammars
    Bauderon, Michel
    Chen, Rui
    Ly, Olivier
    ALGEBRAIC INFORMATICS, 2009, 5725 : 160 - +
  • [7] REDUCTION OF CONTEXT-FREE GRAMMARS
    TANIGUCHI, K
    KASAMI, T
    INFORMATION AND CONTROL, 1970, 17 (01): : 92 - +
  • [8] RELATEDNESS OF CONTEXT-FREE GRAMMARS
    WALTER, HKG
    COMPUTING, 1979, 22 (01) : 31 - 58
  • [9] On restricted context-free grammars
    Dassow, Juergen
    Masopust, Tomas
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2012, 78 (01) : 293 - 304
  • [10] Ordered Context-Free Grammars
    van der Merwe, Brink
    Berglund, Martin
    IMPLEMENTATION AND APPLICATION OF AUTOMATA (CIAA 2022), 2022, 13266 : 53 - 66
12345