On the termination problem for one-rule semi-Thue system

DOI10.1007/3-540-61464-8_61MaRDI QIDQ5055868zbMATH OpenOpenAlexFDO

Authors Géraud Sénizergues

Publication date 9 December 2022

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61464-8_61

zbMATH Keywords

automatic structurefinite automatarational monoidsemi-Thue systemstermination

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Term Rewriting and Applications
• Some undecidable termination problems for semi-Thue systems
• scientific article; zbMATH DE number 49211
• Small Semi-Thue System Universal with Respect to the Termination Problem
• A complete characterization of termination of 0p 1q→1r 0s

Cites work

• A complete characterization of termination of 0p 1q→1r 0s
• Decision problems for semi-Thue systems with a few rules
• Easy multiplications. I: The realm of Kleene's theorem
• Easy multiplications. II: Extensions of rational semigroups
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 49211 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• Termination of rewriting
• Topics in termination

Cited in

(15)

• Almost all one-rule Thue systems have decidable word problems
• A note on a special one-rule semi-Thue system
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Decision problems for semi-Thue systems with a few rules
• scientific article; zbMATH DE number 1615237 (Why is no real title available?)
• On termination of confluent one-rule string-rewriting systems
• On one-rule grid semi-Thue systems
• One-rule semi-Thue systems with loops of length one, two or three
• scientific article; zbMATH DE number 49211 (Why is no real title available?)
• Small Semi-Thue System Universal with Respect to the Termination Problem
• A complete characterization of termination of 0p 1q→1r 0s
• Term Rewriting and Applications
• Semi-Thue systems with an inhibitor
• Termination and derivational complexity of confluent one-rule string-rewriting systems
• Some undecidable termination problems for semi-Thue systems

This page was built for publication: On the termination problem for one-rule semi-Thue system

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