Nachum Dershowitz


PUBLICATIONS ON TERMINATION



  1. Nachum Dershowitz Dec. 2012, “Jumping and Escaping: Modular Termination and the Abstract Path Ordering”, Theoretical Computer Science, Special issue: New Directions in Rewriting (Honoring the 60th Birthday of Yoshihito Toyama), vol. 464, pp. 35-47.
  2. Nachum Dershowitz, May 2009, “On Lazy Commutation”, Languages: From Formal to Natural: Essays Dedicated to Nissim Francez on the Occasion of His 65th Birthday, Orna Grumberg, Michael Kaminski, Shmuel Katz, and Shuly Wintner, eds., Lecture Notes in Computer Science, vol. 5533, Springer-Verlag, Berlin, pp. 59-82.
  3. Nachum Dershowitz and E. Castedo Ellerman, Apr. 2007, “Leanest Quasi-Orderings”, Information and Computation, vol. 205, no. 4, pp. 535-556; available online 23 January 2007. 
  4. Nachum Dershowitz and Georg Moser, “The Hydra Battle Revisited”, June 2007, Rewriting, Computation and Proof -- Essays Dedicated to Jean-Pierre Jouannaud on the Occasion of his 60th Birthday, Lecture Notes in Computer Science, vol. 4600, Springer-Verlag, Berlin, pp. 1-27. 
  5. Nachum Dershowitz and E. Castedo Ellerman, April 2005, “Leanest Quasi-Orderings (Preliminary version)”, Proceedings of the Sixteenth International Conference on Rewriting Techniques and Applications (Nara, Japan), J. Giesl, ed., Lecture Notes in Computer Science, vol. 3467, Springer-Verlag, Berlin, pp. 32-45. 
  6. Nachum Dershowitz, “Open. Closed. Open.”, April 2005, Proceedings of the Sixteenth International Conference on Rewriting Techniques and Applications (Nara, Japan), J. Giesl, ed., Lecture Notes in Computer Science, vol. 3467, Springer-Verlag, Berlin, pp. 376-393. 
  7. Nachum Dershowitz, Sept. 2004, “Termination by Abstraction”, Proceedings of the Twentieth International Conference on Logic Programming, St. Malo, France, Lecture Notes in Computer Science, vol. 3132, Springer-Verlag, Berlin, pp. 1-18.
  8. Nachum Dershowitz, June 2003, “Termination Dependencies” (Extended Abstract), Proceedings of the Sixth International Workshop on Termination (WST '03), A. Rubio, ed., Valencia, Spain, pp. 27-30.
  9. Nachum Dershowitz and Iddo Tzameret, June 2003, “Quasi-Ordered Gap Embedding” (Extended Abstract), June 2003, Proceedings of the Sixth International Workshop on Termination (WST '03), A. Rubio, ed., Valencia, Spain, pp. 30-34.
  10. Nachum Dershowitz and Iddo Tzameret, Aug. 2003, “Gap Embedding for Well-Quasi Orderings”, Proceedings of the 10th Workshop on Logic, Language, Information and Computation, Ouro Preto, Minas Gerais, Brazil; Electronic Notes in Computer Science, vol. 84, pp. 80-90, Sept. 2003.
  11. Nachum Dershowitz and David A. Plaisted, 2001, “Rewriting”, chap. 9 in: Handbook of Automated Reasoning, vol. 1, A. Robinson and A. Voronkov, eds., Elsevier, pp. 535-610. Reviewed in Zbl 0992.68123.
  12. Nachum Dershowitz, editor, May 2001, Extended Abstracts of the Fifth International Workshop on Termination (WST '01), Utrecht, Logic Group Preprint Series No. 209, Institute of Philosophy, Utrecht University, Utrecht, The Netherlands.
  13. Nachum Dershowitz, Naomi Lindenstrauss, Yehoshua Sagiv, and Alexander Serebrenik, May 1999, “When Linear Forms are not Enough” (Abstract), Abstracts of the Fifth International Workshop on Termination, Dagstuhl, Germany.
  14. Nachum Dershowitz, Naomi Lindenstrauss, and Yehoshua Sagiv, May 1997, “What Norms are Useful for Logic Programs?” (Abstract), Extended Abstracts of the Third International Termination Workshop (Ede, The Netherlands), T. Arts, ed., Universiteit Utrecht, Utrecht, The Netherlands.
  15. Nachum Dershowitz, May 1997, “Well-Quasi Orderings and Some Applications” (Abstract), Extended Abstracts of the Third International Termination Workshop (Ede, The Netherlands), T. Arts, ed., Universiteit Utrecht, Utrecht, The Netherlands.
  16. Nachum Dershowitz, June 1997, “Innocuous Constructor-Sharing Combinations”, Proceedings of the Eighth International Conference on Rewriting Techniques and Applications (Sitges, Spain), H. Comon, ed., Lecture Notes in Computer Science, vol. 1232, Springer-Verlag, Berlin, pp. 202-216.
  17. Nachum Dershowitz, Aug. 1997, “When are Two Rewrite Systems More than None?”, Proceedings of the Twenty-Second International Symposium on Mathematical Foundations of Computer Science (Bratislava, Slovakia), I. Pr'ivara and P. Ruzicka, eds., Lecture Notes in Computer Science, vol. 1295, Springer-Verlag, Berlin, pp. 37-43.
  18. Nachum Dershowitz, May 1996, “Trees, Ordinals, and Termination” (Abstract), Proceedings of the 3rd Workshop on Logic, Language, Information and Computation, Salvador, Brazil.
  19. Nachum Dershowitz, 1995, “Contextual Termination” (Abstract), Second International Workshop on Termination, La Bresse, France.
  20. Nachum Dershowitz and Charles Hoot, May 1995, “Natural Termination”, Theoretical Computer Science, vol. 142, no. 2, pp. 179-207. 
  21. Nachum Dershowitz, 1995, “33 Examples of Termination”, in: French Spring School of Theoretical Computer Science Advanced Course on Term Rewriting (Font Romeaux, France, May 1993), H. Comon and J.-P. Jouannaud, eds., Lecture Notes in Computer Science, vol. 909, Springer-Verlag, Berlin, pp. 16-26.
  22. Nachum Dershowitz, 1995, “Hierarchical Termination”, Proceedings of the International Workshop on Conditional and Typed Rewriting Systems (Jerusalem, Israel, July 1994), N. Dershowitz and N. Lindenstrauss, eds., Lecture Notes in Computer Science, vol. 968, Springer-Verlag, Berlin, pp. 89-105.
  23. Nachum Dershowitz, July 1994, “Hierarchical Termination” (Extended Abstract), Abstracts of the International Workshop on Conditional (and Typed) Rewriting Systems, Hebrew University, Jerusalem, Israel.
  24. Nachum Dershowitz and Subrata Mitra, Jan. 1993, “Path Orderings for Termination of Associative-Commutative Rewriting”, Proceedings of the Third International Workshop on Conditional Rewriting Systems (Pont-a-Mousson, France, July 1992), M. Rusinowitch, ed., Lecture Notes in Computer Science, vol. 656, Springer-Verlag, Berlin, pp. 168-174.
  25. Nachum Dershowitz, Apr. 1993, “Trees, Ordinals, and Termination”, Proceedings of the Fourth International Joint Conference on Theory and Practice of Software Development (Orsay, France), M.-C. Gaudel and J.-P. Jouannaud, eds., Lecture Notes in Computer Science, vol. 668, Springer-Verlag, Berlin, pp. 243-250.
  26. Nachum Dershowitz and Charles Hoot, June 1993, “Topics in Termination”, Proceedings of the Fifth International Conference on Rewriting Techniques and Applications (Montreal, Canada), C. Kirchner, ed., Lecture Notes in Computer Science, Berlin, Springer-Verlag.
  27. Nachum Dershowitz and Subrata Mitra, July 1992, “RPO for AC-Termination”, Preliminary Papers of the Third International Workshop on Conditional Rewriting Systems, Pont-a-Mousson, France, M. Rusinowitch, ed., pp. 96-100.
  28. Nachum Dershowitz, June 1991, “Infinite Rewriting” (Abstract), Abstracts of an International Symposium on Theoretical Computer Science in honor of Boris A. Trakhtenbrot, Tel-Aviv University, Tel-Aviv, Israel.
  29. Nachum Dershowitz, June 1991, “Natural Termination Proofs”, Proceedings of the Bar-Ilan Symposium on Foundations of Artificial Intelligence, Bar-Ilan University, Ramat-Gan, Israel.
  30. Nachum Dershowitz, Stéphane Kaplan, and David A. Plaisted, 1991, “Rewrite, Rewrite, Rewrite, Rewrite, Rewrite, ...”, Theoretical Computer Science, vol. 83, no. 1, pp. 71-96. Reviewed in Computing Reviews 9208-0604. 
  31. Nachum Dershowitz, Aug. 1990, “Infinite Rewriting”, Proceedings of Toyohashi Symposium on Theoretical Computer Science, K. Hashiguchi, ed., Toyohashi, Japan, pp. 27-31.
  32. Nachum Dershowitz and Stéphane Kaplan, Jan. 1989, “Rewrite, Rewrite, Rewrite, Rewrite, Rewrite,...”, Proceedings of the Sixteenth ACM Symposium on Principles of Programming Languages, Austin, TX, pp. 250-259.
  33. Nachum Dershowitz, Stéphane Kaplan, and David A. Plaisted, July 1989, “Infinite Normal Forms”, European Association of Theoretical Computer Science, Proceedings of the Sixteenth International Colloquium on Automata, Languages and Programming (Stresa, Italy), Lecture Notes in Computer Science, vol. 372, Springer-Verlag, Berlin, pp. 249-262.
  34. Nachum Dershowitz, Feb./Apr. 1987, “Termination of Rewriting”, J. of Symbolic Computation, vol. 3, no. 1&2, pp. 69-115, Corrigendum: 4, 3 (Dec. 1987), 409-410. Reviewed in Computing Reviews 8810-0792 and Math. Reviews 88j:68099ab.
  35. Nachum Dershowitz, 1987, “Termination of Rewriting”, in: Rewriting Techniques and Applications, pp. 69-115, J.-P. Jouannaud, ed., Academic Press. Reprinted from Journal of Symbolic Computation.
  36. Leo Bachmair, Nachum Dershowitz and Jieh Hsiang, June 1986, “Orderings for Equational Proofs”, Proceedings of the IEEE Symposium on Logic in Computer Science, Cambridge, MA, pp. 346-357. Winner of LICS 2006 “Test-of-time” award.
  37. Leo Bachmair and Nachum Dershowitz, July 1986, “Commutation, Transformation, and Termination”, Proceedings of the Eighth International Conference on Automated Deduction (Oxford, England), J. H. Siekmann, ed., Lecture Notes in Computer Science, vol. 230, Springer-Verlag, Berlin, pp. 5-20. 
  38. Nachum Dershowitz, May 1985, “Termination”, Proceedings of the First International Conference on Rewriting Techniques and Applications (Dijon, France), Lecture Notes in Computer Science, vol. 202, Springer-Verlag, Berlin, pp. 180-224. Reviewed in Zbl 581.68031.
  39. Nachum Dershowitz, Aug. 1985, “Termination of Rewriting”, Report R-85-1220, Department of Computer Science, University of Illinois, Urbana, IL.
  40. Nachum Dershowitz, Oct. 1985, “Completeness of Completion” (Abstract), Bulletin of the European Association for Theoretical Computer Science, vol. 27, pp. 94.
  41. Nachum Dershowitz, May 1983, “Well-Founded Orderings”, Technical Report ATR-83(8478)-3, Office of Information Sciences Research, The Aerospace Corporation, El Segundo, CA.
  42. Nachum Dershowitz, Jieh Hsiang, N. Alan Josephson, and David A. Plaisted, Aug. 1983, “Associative-Commutative Rewriting”, Proceedings of the Eighth International Joint Conference on Artificial Intelligence, Karlsruhe, West Germany, pp. 940-944.
  43. Nachum Dershowitz, Mar. 1982, “Orderings for Term-Rewriting Systems”, Theoretical Computer Science, vol. 17, no. 3, pp. 279-301. Reviewed in Zbl 525.68054. Number 12 on "List of the 100 most cited articles to appear in Theoretical Computer Science". 
  44. Nachum Dershowitz, July 1981, “Termination of Linear Rewriting Systems (Preliminary Version)”, European Association of Theoretical Computer Science, Proceedings of the Eighth International Colloquium on Automata, Languages and Programming (Acre, Israel), Lecture Notes in Computer Science, vol. 115, Springer-Verlag, Berlin, pp. 448-458.
  45. Nachum Dershowitz, 1980, “On the Representation of Ordinals up to Γ0”, Unpublished, Department of Computer Science, University of Illinois, Urbana, IL.
  46. Nachum Dershowitz, Apr. 1979, “A Note on Simplification Orderings”, Report DCS-4-79-986, Department of Computer Science, University of Illinois, Urbana, IL.
  47. Nachum Dershowitz and Zohar Manna, July 1979, “Proving Termination with Multiset Orderings”, Proceedings of the Sixth International EATCS Colloquium on Automata, Languages and Programming (Graz, Austria), Lecture Notes in Computer Science, vol. 71, Springer-Verlag, Berlin, pp. 188-202.
  48. Nachum Dershowitz and Zohar Manna, Aug. 1979, “Proving Termination With Multiset Orderings”, Communications of the ACM, vol. 22, no. 8, pp. 465-476.
  49. Nachum Dershowitz, Aug. 1979, “Orderings for Term-Rewriting Systems”, Report DCS-R-79-987, Department of Computer Science, University of Illinois, Urbana, Il.
  50. Nachum Dershowitz, Oct. 1979, “Orderings for Term-Rewriting Systems”, Proceedings of the Twentieth IEEE Symposium on Foundations of Computer Science, San Juan, PR, pp. 123-131.
  51. Nachum Dershowitz, Nov. 1979, “A Note on Simplification Orderings”, Information Processing Letters, vol. 9, no. 5, pp. 212-215. Reviewed in Math. Reviews 81f:68021. 
  52. Nachum Dershowitz and Zohar Manna, Mar. 1978, “Proving Termination with Multiset Orderings”, Memo AIM-310, STAN-CS-78-651, Stanford Artificial Intelligence Laboratory, Stanford University, Stanford, CA.