The language intersection problem for non-recursive context-free grammars

Mark Jan Nederhof; G. Satta

doi:10.1016/j.ic.2004.03.004

The language intersection problem for non-recursive context-free grammars

Mark Jan Nederhof, G. Satta

School of Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	172-184
Number of pages	13
Journal	Information and Computation
Volume	192
Issue number	2
DOIs	https://doi.org/10.1016/j.ic.2004.03.004
Publication status	Published - 1 Aug 2004

Keywords

formal languages
context-free grammars
computational complexity
parsing algorithms
DECIDABILITY
COMPLEXITY

Access to Document

10.1016/j.ic.2004.03.004

Cite this

@article{2b84e450803c4ed793a782aa2ff887a2,

title = "The language intersection problem for non-recursive context-free grammars",

abstract = "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.",

keywords = "formal languages, context-free grammars, computational complexity, parsing algorithms, DECIDABILITY, COMPLEXITY",

author = "Nederhof, \{Mark Jan\} and G. Satta",

year = "2004",

month = aug,

day = "1",

doi = "10.1016/j.ic.2004.03.004",

language = "English",

volume = "192",

pages = "172--184",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "2",

}

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 - https://www.scopus.com/pages/publications/3042662535

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 -

The language intersection problem for non-recursive context-free grammars

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this