Comments on effective and unambiguous context-free languages
Eduard Kostolanský (1969)
Kybernetika
Similarity:
Eduard Kostolanský (1969)
Kybernetika
Similarity:
Karel Čulík II (1968)
Kybernetika
Similarity:
R. R. Pucella (1997)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Ulrike Brandt, Ghislain Delepine, Hermann K.-G. Walter (2004)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.
Ulrike Brandt, Ghislain Delepine, Hermann K.-G. Walter (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.
Markus Lohrey, Holger Petersen (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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.