TY - JOUR
T1 - The language intersection problem for non-recursive context-free grammars
AU - Nederhof, Mark Jan
AU - Satta, G.
PY - 2004/8/1
Y1 - 2004/8/1
N2 - We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive. (C) 2004 Elsevier Inc. All rights reserved.
AB - We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive. (C) 2004 Elsevier Inc. All rights reserved.
KW - formal languages
KW - context-free grammars
KW - computational complexity
KW - parsing algorithms
KW - DECIDABILITY
KW - COMPLEXITY
UR - http://www.scopus.com/inward/record.url?scp=3042662535&partnerID=8YFLogxK
UR - http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WGK-4C7DCJ7-1&_user=1026342&_handle=V-WA-A-W-D-MsSAYVW-UUW-U-AAZCEDAYEA-AAZBCCWZEA-ZVEDYAVZ-D-U&_fmt=full&_coverDate=08%2F01%2F2004&_rdoc=3&_orig=browse&_srch=%23toc%236825%232004%23998079997%23507049!&_cdi=6825&_acct=C000050565&_version=1&_urlVersion=0&_userid=1026342&md5=56592653faead4706ff0c29d55642522
U2 - 10.1016/j.ic.2004.03.004
DO - 10.1016/j.ic.2004.03.004
M3 - Article
SN - 0890-5401
VL - 192
SP - 172
EP - 184
JO - Information and Computation
JF - Information and Computation
IS - 2
ER -