Commutation-augmented pregroup grammars and push-down automata with cancellation

被引：0

作者：

Francez, Nissim ^{[1
]}

Kaminski, Michael ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

INFORMATION AND COMPUTATION | 2008年 / 206卷 / 9-10期

关键词：

pregroup grammars; commutation; push-down automata; pumping lemma;

D O I：

10.1016/j.ic.2008.03.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The paper proves a pumping lemma for a certain subclass of mildly context-sensitive languages, the one defined by commutation-augmented pregroup grammars; in addition, an automaton equivalent to such grammars is introduced, augmenting push-down automata by cancellation in the bottom of its stack. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：1018 / 1032

页数：15

共 12 条

[1] Aho A. V., 1972, THEORY PARSING TRANS
[2] BUSZKOWSKI W, 2001, LNCS LNAI, V2099, P95
[3] BUSZKOWSKI W, 2007, PRE P INT WORKSH NON
[4] Commutation-augmented pregroup grammars and mildly context-sensitive languages
Francez N.
Kaminski M.
[J]. Studia Logica, 2007, 87 (2-3) : 295 - 321
[5] FRANCEZ N, 2007, PRE P 1 INTC LANG AU, P7
[6] Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation
[7] Joshi A. K., 1997, Handbook of Formal Languages, P69, DOI DOI 10.1007/978-3-642-59126-6_2
[8] Joshi Aravind K., 1985, Natural Language Processing: Theoretical. Computational and Psychological Perspectives, P206, DOI [10.1017/CBO9780511597855.007, DOI 10.1017/CBO9780511597855]
[9] Type grammar revisited
Lambek, J
[J]. LOGICAL ASPECTS OF COMPUTATIONAL LINGUISTICS, 1999, 1582 : 1 - 27
[10] MERY B, 2006, 6042 INRIA

← 1 2 →