Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Complexity results for prefix grammars

Markus LohreyHolger Petersen — 2005

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

Complexity results for prefix grammars

Markus LohreyHolger Petersen — 2010

RAIRO - Theoretical Informatics and Applications

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

Page 1

Download Results (CSV)