Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems | Zendy

Yi Wang | Zendy; Masahiko Sakai | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems

Author(s) -

Yi Wang,

Masahiko Sakai

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-36834-5

DOI - 10.1007/11805618_26

Subject(s) - decidability , computer science , rewriting , dependency graph , dependency (uml) , term (time) , theoretical computer science , graph , programming language , physics , software engineering , quantum mechanics

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research