Decidability of termination of grid string rewriting rules

DOI10.1137/S009753979833297XMaRDI QIDQ2784496zbMATH OpenOpenAlexFDO

Authors Alfons Geser

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979833297x

zbMATH Keywords

grid ruleone-rulesemi-Thue systemstring rewriting systemterminationtotal division order

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Reducing the gradedness problem of string rewriting systems to a termination problem
• scientific article; zbMATH DE number 3928342
• A new decidability technique for ground term rewriting systems with applications
• On termination of confluent one-rule string-rewriting systems
• Termination proofs for string rewriting systems via inverse match-bounds
• Termination and derivational complexity of confluent one-rule string-rewriting systems
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Decidability of reachability for disjoint union of term rewriting systems
• Decidable approximations of term rewriting systems
• Termination proofs for ground rewrite systems -- interpretations and derivational complexity

Cited in

(8)

• Decision problems for semi-Thue systems with a few rules
• On prefixal one-rule string rewrite systems
• Reverse mathematical bounds for the termination theorem
• scientific article; zbMATH DE number 2043544 (Why is no real title available?)
• scientific article; zbMATH DE number 2090078 (Why is no real title available?)
• A canonical automaton for one-rule length-preserving string rewrite systems
• On rationally controlled one-rule insertion systems
• Grid structures and undecidable constraint theories

This page was built for publication: Decidability of termination of grid string rewriting rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784496)