Recherche et téléchargement d’archives de revues mathématiques numérisées

 
 
  Table des matières de ce fascicule | Article précédent | Article suivant
Geser, Alfons; Zantema, Hans
Non-looping string rewriting. Informatique théorique et applications, 33 no. 3 (1999), p. 279-301
Texte intégral djvu | pdf | Analyses MR 1728428 | Zbl 0951.68054

URL stable: http://www.numdam.org/item?id=ITA_1999__33_3_279_0

Bibliographie

[1] S. Adjan and G. Oganesjan, Problems of equality and divisibility in semigroups with a single defining relation. Mat. Zametki 41 (1987) 412-421.  Zbl 0617.20035
[2] R. Book and F. Otto, String-rewriting systems. Texts and Monographs in Computer Science. Springer, New York (1993).  MR 1215932 |  Zbl 0832.68061
[3] N. Dershowitz, Termination of linear rewriting Systems. In Proc. of the 8th International Colloquium on Automata, Languages and Programming (ICALP81), Springer, Lecture Notes in Computer Science 115 (1981) 448-458.  MR 826061 |  Zbl 0465.68009
[4] N. Dershowitz, Termination of rewriting. J. Symb. Comput. 3 (1987) 69-115; Corrigendum 4 (1987) 409-410.  MR 893186
[5] N. Dershowitz and C. Hoot, Natural termination. Theoret. Comput. Sci. 142 (1995) 179-207.  MR 1334808 |  Zbl 0873.68103
[6] M. Ferreira and H. Zantema, Dummy elimination: Making termination easier. In Proc. l0th Conf. Fundamentals of Computation Theory, H. Reichel, Ed., Springer, Lecture Notes in Computer Science 965 (1995) 243-252.  MR 1459181
[7] A. Geser, Termination of one-rule string rewriting Systems l → r where |r| ≤ 9. Tech. Rep., Universität Tübingen, D (Jan. 1998).
[8] J. V. Guttag, D. Kapur and D. R. Musser, On proving uniform termination and restricted termination of rewriting systems. SIAM J. Comput. 12 (1983) 189-214.  MR 687810 |  Zbl 0526.68036
[9] G. Huet and D. S. Lankford, On the uniform halting problem for term rewriting Systems. Rapport Laboria 283, INRIA (1978).
[10] M. Jantzen, Confluent string rewriting, Vol. 14 of EATCS Monographs on Theoretical Computer Science. Springer, Berlin (1988).  MR 972260 |  Zbl 1097.68572
[11] Y. Kobayashi, M. Katsura and K. Shikishima-Tsuji, Termination and derivational complexity of confluent one-rule string rewriting Systems. Tech. Rep., Dept. of Computer Science, Toho University, JP (1997).
[12] W. Kurth, Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel. Dissertation, Technische Universität Clausthal, Germany (1990).  Zbl 0719.03019
[13] W. Kurth, One-rule semi-Thue Systems with loops of length one, two, or three. RAIRO Theoret. Informatics Appl. 30 (1995) 415-429.
Numdam |  Zbl 0867.68064
[14] D. S. Lankford and D. R. Musser, A finite termination criterion. Tech. Rep., Information Sciences Institute, Univ. of Southern California, Marina-del-Rey, CA (1978).
[15] Y. Matiyasevitch and G. Sénizergues, Decision problems for semi-Thue systems with a few rules. In IEEE Symp. Logic in Computer Sdence'96 (1996).
[16] R. McNaughton, The uniform halting problem for one-rule Semi-Thue Systems. Tech. Rep. 94-18, Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, Aug. 1994.
See also "Correction to The Uniform Halting Problem for One-rule Semi-Thue Systems", Personal communication (Aug. 1996).
[17] R. McNaughton, Well-behaved derivations in one-rule Semi-Thue Systems. Tech. Rep. 95-15, Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY (Nov. 1995).
[18] R. McNaughton, Semi-Thue Systems with an inhibitor. Tech. Rep. 97-5, Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY (1 1997).
[19] F. Otto, The undecidability of self-embedding for finite semi-Thue and Thue Systems. Theoret. Comput. Sci. 47 (1986) 225-232.  MR 881214 |  Zbl 0624.03032
[20] B.K. Rosen, Tree-manipulating Systems and Church-Rosser Theorems.J. ACM 20 (1973). 160-187.  MR 331850 |  Zbl 0267.68013
[21] K. Shikishima-Tsuji, M. Katsura and Y. Kobayashi, On termination of confluent one-rule string rewriting Systems. Inform. Process, Lett. 61 (1997), 91-96.  MR 1439874
[22] C. Wrathall, Confluence of one-rule Thue Systems. In Word Equations and Related Topics, K.U. Schulz, Ed., Springer, Lecture Notes in Computer Science 572 (1991).  MR 1232039
[23] H. Zantema and A. Geser, A complete characterization of termination of 0p1q → lr0s. Applicable Algebra in Engineering, Communication, and Computing. In print.  Zbl 0962.68086
[24] H. Zantema and A. Geser, A complete characterization of termination of 0p1q → lr0s. In Proc. of the 6th Conference on Rewriting Techniques and Applications, J. Hsiang, Ed., Springer, Lecture Notes in Computer Science 914 (1995) 41-55.
Copyright Cellule MathDoc 2014 | Crédit | Plan du site