Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2005__39_2_391_0,
author = {Lohrey, Markus and Petersen, Holger},
title = {Complexity results for prefix grammars},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {391--401},
publisher = {EDP-Sciences},
volume = {39},
number = {2},
year = {2005},
doi = {10.1051/ita:2005024},
mrnumber = {2142119},
zbl = {1133.68357},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005024/}
}
TY - JOUR AU - Lohrey, Markus AU - Petersen, Holger TI - Complexity results for prefix grammars JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 391 EP - 401 VL - 39 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005024/ DO - 10.1051/ita:2005024 LA - en ID - ITA_2005__39_2_391_0 ER -
%0 Journal Article %A Lohrey, Markus %A Petersen, Holger %T Complexity results for prefix grammars %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 391-401 %V 39 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005024/ %R 10.1051/ita:2005024 %G en %F ITA_2005__39_2_391_0
Lohrey, Markus; Petersen, Holger. Complexity results for prefix grammars. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 2, pp. 391-401. doi: 10.1051/ita:2005024
Cité par Sources :