Ordered Context-Free Grammars Revisited

被引：0

作者：

van der Merwe, Brink ^{[1
]}

机构：

[1] Stellenbosch Univ, Dept Comp Sci, Stellenbosch, South Africa

来源：

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2023年 / 388卷

关键词：

Ordered context-free grammars; Unambiguous grammar formalisms; Shared packed parse forests; EXPRESSION; POWER;

D O I：

10.4204/EPTCS.388.13

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We continue our study of ordered context-free grammars, a grammar formalism that places an order on the parse trees produced by the corresponding context-free grammar. In particular, we simplify our previous definition of a derivation of a string for a given ordered context-free grammar, and present a parsing algorithm, using shared packed parse forests, with time complexity O(n(4)), where n is the length of the input string being parsed.

引用

页码：140 / 153

页数：14

共 11 条

[1] Ordered Context-Free Grammars [J].

van der Merwe, Brink ;

Berglund, Martin .

IMPLEMENTATION AND APPLICATION OF AUTOMATA (CIAA 2022), 2022, 13266 :53-66

[2] Distributional Learning of Simple Context-Free Tree Grammars [J].

Kasprzik, Anna ;

Yoshinaka, Ryo .

ALGORITHMIC LEARNING THEORY, 2011, 6925 :398-+

[3] A Generalization of Linear Indexed Grammars Equivalent to Simple Context-Free Tree Grammars [J].

Kanazawa, Makoto .

FORMAL GRAMMAR, FG 2014, 2014, 8612 :86-103

[4] The Pumping Lemma for Well-Nested Multiple Context-Free Languages [J].

Kanazawa, Makoto .

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS, 2009, 5583 :312-325

[5] Interpretable and context-free deconvolution of multi-scale whole transcriptomic data with UniCell deconvolve [J].

Charytonowicz, Daniel ;

Brody, Rachel ;

Sebra, Robert .

NATURE COMMUNICATIONS, 2023, 14 (01)

[6] Free, unlinked glycosylphosphatidylinositols on mammalian cell surfaces revisited [J].

Wang, Yicheng ;

Hirata, Tetsuya ;

Maeda, Yusuke ;

Murakami, Yoshiko ;

Fujita, Morihisa ;

Kinoshita, Taroh .

JOURNAL OF BIOLOGICAL CHEMISTRY, 2019, 294 (13) :5038-5049

[7] Public opinion change after the Fukushima nuclear accident: The role of national context revisited [J].

Latre, Edwin ;

Perko, Tanja ;

Thijssen, Peter .

ENERGY POLICY, 2017, 104 :124-133

[8] Before Hegemony: Britain, Free Trade, and Nineteenth-Century World Order Revisited [J].

Lacher, Hannes ;

Germann, Julian .

INTERNATIONAL STUDIES REVIEW, 2012, 14 (01) :99-124

[9] Mining-free territories and decolonial theory: Evaluating the synergies in the Brazilian context [J].

Vilani, Rodrigo Machado ;

Milanez, Bruno ;

Martins, Marcia Barbosa ;

de Oliveira, Maria Amalia Silva Alves ;

Machado, Carlos Jose Saldanha ;

de Oliveira, Marilia Luisa .

EXTRACTIVE INDUSTRIES AND SOCIETY, 2024, 17

[10] The biological feasibility and social context of gene-edited, caffeine-free coffee [J].

Leibrock, Nils V. ;

Santegoets, Joris ;

Mooijman, Paul J. W. ;

Yusuf, Filemon ;

Zuijdgeest, Xander C. L. ;

Zutt, Esmee A. ;

Jacobs, Josette G. M. ;

Schaart, Jan G. .

FOOD SCIENCE AND BIOTECHNOLOGY, 2022, 31 (06) :635-655

← 1 2 →