Decidability of Termination for Semi-Constructor TRSs, Left-Linear Shallow TRSs and Related Systems Decidability of termination for semi-constructor TRSs, left-linear shallow TRSs and related systems

Access this Article

Abstract

We consider several classes of term rewriting systems and prove that termination is decidable for these classes. By showing the cycling property of infinite dependency chains, we prove that termination is decidable for semi-constructor case, which is a superclass of right-ground TRSs. By analyzing argument propagation cycles in the dependency graph, we show that termination is also decidable for left-linear shallow TRSs. Moreover we extend these by combining these two techniques.

Journal

  • Proceedings of 17th Int'l Conference on Term Rewriting and Applications

    Proceedings of 17th Int'l Conference on Term Rewriting and Applications, 343-356, 2006-09

    Springer

Cited by:  2

Codes

  • NII Article ID (NAID)
    120000975763
  • Text Lang
    ENG
  • Article Type
    Proceedings
  • Data Source
    CJPref  IR 
Page Top