Geodesic
Reducing the gradedness problem of string rewriting systems to a termination problem
Stein, Itamar1
1 Department of Mathematics, Bar Ilan University, 52900 Ramat Gan, Israel
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 233-254

Voir la notice de l'article provenant de la source Numdam

A finite string rewriting system (SRS) is called graded if every word over its alphabet is equivalent to only a finite number of other words. We consider the problem of deciding whether a given finite SRS is graded. We show that, in general, this problem is not decidable. Moreover we show that for many SRSs (including all one-rule SRSs), one can convert the SRS to another SRS such that the original one is graded if and only if the converted one is terminating. Since there are computer programs that can decide for many cases whether a given SRS is terminating or not, this can give us a method to prove automatically if a given SRS is graded or not.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2015008
Classification : 68Q42
Keywords: String rewriting, termination, gradedness

Stein, Itamar 1

1 Department of Mathematics, Bar Ilan University, 52900 Ramat Gan, Israel 
@article{ITA_2015__49_3_233_0,
     author = {Stein, Itamar},
     title = {Reducing the gradedness problem of string rewriting systems to a termination problem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {233--254},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {3},
     year = {2015},
     doi = {10.1051/ita/2015008},
     mrnumber = {3434600},
     zbl = {1347.68201},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2015008/}
}
TY  - JOUR
AU  - Stein, Itamar
TI  - Reducing the gradedness problem of string rewriting systems to a termination problem
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2015
SP  - 233
EP  - 254
VL  - 49
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2015008/
DO  - 10.1051/ita/2015008
LA  - en
ID  - ITA_2015__49_3_233_0
ER  - 
%0 Journal Article
%A Stein, Itamar
%T Reducing the gradedness problem of string rewriting systems to a termination problem
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2015
%P 233-254
%V 49
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2015008/
%R 10.1051/ita/2015008
%G en
%F ITA_2015__49_3_233_0
Stein, Itamar. Reducing the gradedness problem of string rewriting systems to a termination problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 233-254. doi: 10.1051/ita/2015008

Cité par Sources :