Small Semi-Thue System Universal with Respect to the Termination Problem

DOI10.3233/FI-2017-1559MaRDI QIDQ4601128zbMATH OpenOpenAlexFDO

Authors Reino Niskanen, Vesa Halava, Yu. Matiyasevich

Publication date 19 January 2018

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2017-1559

zbMATH Keywords

semi-Thue systemtermination problemundecidabilityuniversal semi-Thue system

Mathematics Subject Classification ID

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

Recommendations

• Some undecidable termination problems for semi-Thue systems
• On the termination problem for one-rule semi-Thue system
• Small Semi-Weakly Universal Turing Machines
• Small Semi-weakly Universal Turing Machines
• Some generalized semi-thue systems
• Deterministic semi-Thue systems and variants of Post correspondence problem
• Small universal numerical P systems with thresholds for computing functions
• The undecidability of self-embedding for finite semi-Thue and Thue systems
• Word problem for deterministic and reversible semi-Thue systems

Cited in

(7)

• Decision problems for semi-Thue systems with a few rules
• On the termination problem for one-rule semi-Thue system
• Term Rewriting and Applications
• Semi-Thue systems with an inhibitor
• Integer Weighted Automata on Infinite Words
• Some undecidable termination problems for semi-Thue systems
• Integer weighted automata on infinite words

This page was built for publication: Small Semi-Thue System Universal with Respect to the Termination Problem

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