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

DOI10.1007/3-540-61464-8_61zbMATH Open1503.68155OpenAlexW1503994260MaRDI QIDQ5055868FDOQ5055868

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Termination of rewriting
• Decision problems for semi-Thue systems with a few rules
• Title not available (Why is that?)
• Title not available (Why is that?)
• A complete characterization of termination of 0p 1q→1r 0s
• Title not available (Why is that?)
• Easy multiplications. I: The realm of Kleene's theorem
• Easy multiplications. II: Extensions of rational semigroups
• Topics in termination

Cited In (14)

• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Some undecidable termination problems for semi-Thue systems
• On one-rule grid semi-Thue systems
• A complete characterization of termination of 0p 1q→1r 0s
• Title not available (Why is that?)
• On termination of confluent one-rule string-rewriting systems
• A note on a special one-rule semi-Thue system
• Title not available (Why is that?)
• Decision problems for semi-Thue systems with a few rules
• Almost all one-rule Thue systems have decidable word problems
• Small Semi-Thue System Universal with Respect to the Termination Problem
• Term Rewriting and Applications
• Semi-Thue systems with an inhibitor
• Termination and derivational complexity of confluent one-rule string-rewriting 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)