Word problem for deterministic and reversible semi-Thue systems
From MaRDI portal
Publication:2247995
DOI10.1007/S00233-013-9550-3zbMATH Open1361.03035OpenAlexW2038666277MaRDI QIDQ2247995FDOQ2247995
Publication date: 30 June 2014
Published in: Semigroup Forum (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00233-013-9550-3
Recommendations
Automata and formal grammars in connection with logical questions (03D05) Thue and Post systems, etc. (03D03) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35)
Cites Work
- Logical Reversibility of Computation
- Decision problems for semi-Thue systems with a few rules
- A note on Post's correspondence problem
- Title not available (Why is that?)
- Recursive Unsolvability of a problem of Thue
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (11)
- The undecidability of self-embedding for finite semi-Thue and Thue systems
- Title not available (Why is that?)
- Decision problems for semi-Thue systems with a few rules
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- Title not available (Why is that?)
- Almost all one-rule Thue systems have decidable word problems
- On the \(n\)-permutation Post correspondence problem
- Small Semi-Thue System Universal with Respect to the Termination Problem
- Title not available (Why is that?)
- New proof for the undecidability of the circular PCP
- The Thue problem and logical specifications of derivation in formal systems
This page was built for publication: Word problem for deterministic and reversible semi-Thue systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2247995)
