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

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

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 languageEnglish
Pages (from-to)172-184
Number of pages13
JournalInformation and Computation
Volume192
Issue number2
DOIs
Publication statusPublished - 1 Aug 2004

Keywords

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

Fingerprint

Dive into the research topics of 'The language intersection problem for non-recursive context-free grammars'. Together they form a unique fingerprint.

Cite this