One-rule semi-Thue systems with loops of length one, two or three

Winfried Kurth

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

  • Volume: 30, Issue: 5, page 415-429
  • ISSN: 0988-3754

How to cite

top

Kurth, Winfried. "One-rule semi-Thue systems with loops of length one, two or three." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.5 (1996): 415-429. <http://eudml.org/doc/92543>.

@article{Kurth1996,
author = {Kurth, Winfried},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {semi-Thue system},
language = {eng},
number = {5},
pages = {415-429},
publisher = {EDP-Sciences},
title = {One-rule semi-Thue systems with loops of length one, two or three},
url = {http://eudml.org/doc/92543},
volume = {30},
year = {1996},
}

TY - JOUR
AU - Kurth, Winfried
TI - One-rule semi-Thue systems with loops of length one, two or three
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 5
SP - 415
EP - 429
LA - eng
KW - semi-Thue system
UR - http://eudml.org/doc/92543
ER -

References

top
  1. 1. H. ABDULRAB, Solving Word Equations, RAIRO Theo. Informatics and Appl., 1990, 24, pp. 109-130. Zbl0701.68053MR1073531
  2. 2. A. C. CARON, Linear Bounded Automata and Rewrite Systems: Influence of Initial Configurations on Decision Properties. Proceedings of TAPSOFT 91, April 8-12, 1991, Brighton, England, LNCS, 1991, 493, pp. 74-89. Zbl0967.68523MR1107773
  3. 3. M. DAUCHET, Termination of Rewriting is Undecidable in the One-rule Case. Proc. 13th Symposium MFCS, August 29-Sept. 2, 1988, Carlsbad, Czech., LNCS, 1988, 324, pp. 262-270. Zbl0649.68026MR1023430
  4. 4. N. DERSHOWITZ, Termination of Rewriting. J. Symbolic Computation, 1987, 3, pp. 69-116, and 1987, 4, pp. 409-410. Zbl0637.68035MR925736
  5. 5. C. KIRCHNER (Ed.), Rewriting Techniques and Applications, Proceedings of RTA-93, June 16-18, 1993, Montréal, Canada. LNCS, 1993, 690. Zbl0825.00068MR1251780
  6. 6. W. KURTH, Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel, Dissertation, Technische Universität Clausthal, 1990. Zbl0719.03019
  7. 7. G. LALLEMENT, On Monoids Presented by a Single Relation. J. Algebra, 1974, 32, pp. 370-388. Zbl0307.20034MR354908
  8. 8. R. MCNAUGHTON, The Uniform Halting Problem for One-Rule Semi-Thue Systems, Rensselaer Polytechnic Institute, Report 94-18, August 1994. 
  9. 9. R. MCNAUGHTON, Well Behaved Derivations in One-Rule Semi-Thue Systems, Rensselaer Polytechnic Institute, Report 95-15, November 1995. 
  10. 10. Y. METIVIER, Calcul de Longueurs de Chaînes de Réécriture dans le Monoïde Libre, Theoretical Computer Science, 1985, 35, pp. 71-87. Zbl0562.03019MR785908
  11. 11. P. NARENDRAN, C. Ó'DUNLAING and H. ROLLETSCHEK, Complexity of Certain Decision Problems About Congruential Languages, J. Computer Syst. Sci., 1985, 30, pp. 343-358. Zbl0607.68055MR805653
  12. 12. F. OTTO, The Undecidability of Self-Embedding for Finite Semi-Thue and Thue Systems, Theoretical Computer Science, 1986, 47, pp. 225-232. Zbl0624.03032MR881214
  13. 13. H. ZANTEMA and A. GESER, A complete characterization of termination of 0p 1q → 1r 0s. Proceedings of RTA-95, April 5-7, 1995, Kaiserslautern, Germany, LNCS, 1995, 914, pp. 41-55. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.