Undecidable Properties on Length-Two String Rewriting Systems | Zendy

Masahiko Sakai | Zendy; Yi Wang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Undecidable Properties on Length-Two String Rewriting Systems

Author(s) -

Masahiko Sakai,

Yi Wang

Publication year - 2008

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2008.03.053

Subject(s) - undecidable problem , rewriting , confluence , string (physics) , mathematics , class (philosophy) , term (time) , discrete mathematics , decidability , computer science , programming language , physics , quantum mechanics , artificial intelligence , mathematical physics

Length-two string rewriting systems are length-preserving string rewriting systems that consist of length-two rules. This paper shows that confluence, termination, left-most termination and right-most termination are undecidable properties for length-two string rewriting systems. These results mean that these properties are undecidable for the class of linear term rewriting systems in which depth-two variables are allowed in both sides of rules

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