Some undecidable termination problems for semi-Thue systems

DOI10.1016/0304-3975(94)00278-9zbMath0873.68054OpenAlexW1993963635MaRDI QIDQ673625

Géraud Sénizergues

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00278-9

zbMATH Keywords

semi-Thue system

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)

Related Items (max. 100)

Integer weighted automata on infinite words ⋮ Integer Weighted Automata on Infinite Words ⋮ Quasi-interpretations. A way to control resources ⋮ Decision problems for semi-Thue systems with a few rules

Cites Work

• Homogeneous Thue systems and the Church-Rosser property
• A simple presentation of a group with unsolvable word problem
• Termination of rewriting
• A note on Post's correspondence problem
• Cancellation rules and extended word problems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Simulation of Turing machines by a left-linear rewrite rule
• The undecidability of the Turing machine immortality problem
• Word and conjugacy problems in groups with only a few defining relations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some undecidable termination problems for semi-Thue systems