Research Article
On the Termination Problem for String Rewrite Systems
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 146 - Issue 6 |
| Published: Jul 2016 |
| Authors: Nacer Ghadbane, Douai Mihoubi |
10.5120/ijca2016910811
|
Nacer Ghadbane, Douai Mihoubi . On the Termination Problem for String Rewrite Systems. International Journal of Computer Applications. 146, 6 (Jul 2016), 28-30. DOI=10.5120/ijca2016910811
@article{ 10.5120/ijca2016910811,
author = { Nacer Ghadbane,Douai Mihoubi },
title = { On the Termination Problem for String Rewrite Systems },
journal = { International Journal of Computer Applications },
year = { 2016 },
volume = { 146 },
number = { 6 },
pages = { 28-30 },
doi = { 10.5120/ijca2016910811 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2016
%A Nacer Ghadbane
%A Douai Mihoubi
%T On the Termination Problem for String Rewrite Systems%T
%J International Journal of Computer Applications
%V 146
%N 6
%P 28-30
%R 10.5120/ijca2016910811
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Based on some result given in [2], concerning the termination of a semi-Thue systeme, we give some results illustrated by some examples to give some Noetherian semi-Thue systems.
References
- Berstel & D. Perrin. "Theoryofcodes", Academic Press (1984).
- R. V. Book, F. Otto, "String-Rewriting Systems", Springer-Verlag, (1993).
- N. Dershowitz, "Termination of Rewriting", Jornal of Symbolic Computation,vol 3, pp. 69-116, (1987).
- M. Eytan, G. TH. Guilbaud, Présentation de quelques monoïdes finis. Mathématiques et sciences humaines, vol,7, pp. 3-10, (1964).
- R. Floyd, R. Beigel, Traduction de D. Krob, "Le langage des machines", International Thomson France, paris, (1995).
- Y. Metivier, "Calcul de longueurs de chaînes de réécriture dans le monoïde libre", Theoretical Computer Science, vol 35, pp. 71-87, (1985).
- Y. Lafont, "A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)", Journal of Pur and Applied Algebra, vol 98, pp. 229-244, (1995).
- Y. Lafont, "Réécritue et problème du mot", Gazette des Mathématiciens, pp. 27-38, (2009).
- Y. Lafont. Algebra and Geometry of Rewrtiting. Laboratoire de Mathématiques Discrètes de Luminy, Marseille, France. (2006).
- M. Lohrey, " The Compressed Word Problem for Groups", Springer (2014).
- M. Nivat. Sur le noyau d'un morphisme du monoïde libre, Proceedings de Séminaire Schutzenberger, vol 1, pp. 1-6, (1970).
- D. Kapur and P. Narendran,A Finite Thue System With Decidable Word Problem And Without Equivalent Finite Canonical System", Theoretical Computer Science, vol 35, pp. 337-344, (1985).
- M. Nivat. Sur le noyau d'un morphisme du monoïde libre, Séminaire Schutzenberger, tom 1 (1969/1970), exp. N0 4, p. 1-6.
- J. Rouyer. Preuves de terminaison de systèmes de réécriture fondées sur les interprétations polynomiales. CRIN, Nancy, (1989).
- H. Zantema, Termination of String Rewriting Proved Automatically, TU Eindhoven, (2004).
Index Terms
Keywords