On termination of confluent one-rule string-rewriting systems

DOI10.1016/S0020-0190(96)00200-1MaRDI QIDQ286976zbMATH OpenOpenAlexFDO

Authors Kayoko Shikishima-Tsuji, Masashi Katsura, Yuji Kobayashi

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(96)00200-1

zbMATH Keywords

confluent systemdecidabilitystring-rewriting systemtermination problem

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Termination and derivational complexity of confluent one-rule string-rewriting systems
• Term Rewriting and Applications
• scientific article; zbMATH DE number 2043544
• A complete characterization of termination of 0p 1q→1r 0s
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)

Cites work

• A complete characterization of termination of 0p 1q→1r 0s
• Confluence of one-rule Thue systems
• Decision problems for semi-Thue systems with a few rules
• scientific article; zbMATH DE number 4071228 (Why is no real title available?)
• scientific article; zbMATH DE number 49211 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• On the termination problem for one-rule semi-Thue system
• ON THE WORD AND DIVISIBILITY PROBLEMS IN SEMIGROUPS WITH A SINGLE DEFINING RELATION
• Simulation of Turing machines by a left-linear rewrite rule
• Termination of rewriting

Cited in

(18)

• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• On normalizing, non-terminating one-rule string rewriting systems
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• A Lyndon's identity theorem for one-relator monoids
• Decidability of termination of grid string rewriting rules
• Reducing the gradedness problem of string rewriting systems to a termination problem
• scientific article; zbMATH DE number 49211 (Why is no real title available?)
• scientific article; zbMATH DE number 2043544 (Why is no real title available?)
• scientific article; zbMATH DE number 2090078 (Why is no real title available?)
• On confluence of one-rule trace-rewriting systems
• A canonical automaton for one-rule length-preserving string rewrite systems
• Diamond Subgraphs in the Reduction Graph of a One-Rule String Rewriting System
• A complete characterization of termination of 0p 1q→1r 0s
• Sparse tiling through overlap closures for termination of string rewriting
• Termination of cycle rewriting
• Term Rewriting and Applications
• Termination and derivational complexity of confluent one-rule string-rewriting systems
• Adding constants to string rewriting

This page was built for publication: On termination of confluent one-rule string-rewriting systems

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