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

finite automataterminationsemi-Thue systemsautomatic structurerational monoid

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Termination of rewriting
• Topics in termination

Cited in

(14)

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

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)