Termination of String Rewriting Rules That Have One Pair of Overlaps | SpringerLink
Skip to main content
Springer Nature Link
Log in

Termination of String Rewriting Rules That Have One Pair of Overlaps

  • Conference paper
  • First Online:
Rewriting Techniques and Applications (RTA 2003)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2706))

Included in the following conference series:

  • 340 Accesses

Abstract

This paper presents a partial solution to the long standing open problem whether termination of one-rule string rewriting is decidable. Overlaps between the two sides of the rule play a central role in existing termination criteria. We characterize termination of all one-rule string rewriting systems that have one such overlap at either end. This both completes a result of Kurth and generalizes a result of Shikishima-Tsuji et al.

This work was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-97046 while the author was in residence at ICASE, NASA Langley Research Center, Hampton, VA 23681-2199, USA.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. N. Dershowitz, Termination of linear rewriting systems, in Proc. 8th Int. Coll. Automata, Languages and Programming, LNCS 115, Springer, 1981, pp. 448–458.

    Google Scholar 

  2. A. Geser, Decidability of termination of grid string rewriting rules, SIAM J. Comput., 31 (2002), pp. 1156–1168.

    Article  MATH  MathSciNet  Google Scholar 

  3. —, Is termination decidable for string rewriting with only one rule?, habilitation thesis, Wilhelm-Schickard-Institut, Universität Tübingen, Germany, Jan. 2002. 201 pages.

    Google Scholar 

  4. —, Loops of superexponential lengths in one-rule string rewriting, in Proc. 13th Int. Conf. Rewriting Techniques and Applications, S. Tison, ed., LNCS 2378, Springer, 2002, pp. 267–280.

    Chapter  Google Scholar 

  5. M. Hermann, Divergence des systèmes de réécriture et schématisation des ensembles infinis de termes, habilitation, Université de Nancy, France, Mar. 1994.

    Google Scholar 

  6. Y. Kobayashi, M. Katsura, and K. Shikishima-Tsuji, Termination and derivational complexity of confluent one-rule string rewriting systems, Theoret. Comput. Sci., 262 (2001), pp. 583–632.

    Article  MATH  MathSciNet  Google Scholar 

  7. W. Kurth, Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel, dissertation, Technische Universität Clausthal, Germany, 1990.

    MATH  Google Scholar 

  8. —, One-rule semi-Thue systems with loops of length one, two, or three, RAIRO Inform. Théor., 30 (1995), pp. 415–429.

    Google Scholar 

  9. 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.

    Google Scholar 

  10. 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’”, unpublished paper, Aug., 1996.

    Google Scholar 

  11. —, Well-behaved derivations in one-rule Semi-Thue Systems, Tech. Rep. 95-15, Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, Nov. 1995. See also “Correction by the author to ‘Well-behaved derivations in one-rule Semi-Thue Systems’”, unpublished paper, July, 1996.

    Google Scholar 

  12. —, Semi-Thue Systems with an Inhibitor, J. Automated Reasoning, 26 (1997), pp. 409–431.

    Google Scholar 

  13. W. Moczydłowski, Jr and A. Geser, Termination of single-threaded one-rule Semi-Thue systems, Tech. Rep. TR 02-08 (273), Warsaw University, Dec. 2002. Available electronically at http://www.research.nianet.org/~geser/papers/single.html.

  14. G. Sénizergues, On the termination problem for one-rule Semi-Thue Systems, in Proc. 7th Int. Conf. Rewriting Techniques and Applications, H. Ganzinger, ed., LNCS 1103, Springer, 1996, pp. 302–316.

    Google Scholar 

  15. K. Shikishima-Tsuji, M. Katsura, and Y. Kobayashi, On termination of confluent one-rule string rewriting systems, Inform. Process. Lett., 61 (1997), pp. 91–96.

    Article  MathSciNet  Google Scholar 

  16. C. Wrathall, Confluence of one-rule Thue systems, in Word Equations and Related Topics, K. U. Schulz, ed., LNCS 572, Springer, 1992.

    Google Scholar 

  17. H. Zantema and A. Geser, A complete characterization of termination of 0p1q → 1r0s, Applicable Algebra in Engineering, Communication, and Computing, 11 (2000), pp. 1–25.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National Institute for Aerospace, 144 Research Drive, Hampton, VA, 23666, USA

    Alfons Geser

Authors
  1. Alfons Geser
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dpt. Lenguajes y Sistemas Informáticos (LSI), Technical University of Catalonia (UPC), Jordi Girona 1, 08034, Barcelona, Spain

    Robert Nieuwenhuis

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Geser, A. (2003). Termination of String Rewriting Rules That Have One Pair of Overlaps. In: Nieuwenhuis, R. (eds) Rewriting Techniques and Applications. RTA 2003. Lecture Notes in Computer Science, vol 2706. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44881-0_29

Download citation

  • DOI: https://doi.org/10.1007/3-540-44881-0_29

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40254-1

  • Online ISBN: 978-3-540-44881-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics