Decision problems for semi-Thue systems with a few rules
From MaRDI portal
Publication:1763707
DOI10.1016/j.tcs.2004.09.016zbMath1078.03033OpenAlexW2098677925MaRDI QIDQ1763707
Géraud Sénizergues, Yu. V. Matiyasevich
Publication date: 22 February 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.09.016
Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)
Related Items
On termination of confluent one-rule string-rewriting systems, Automatic sequences of rank two, Integer weighted automata on infinite words, A Lyndon's identity theorem for one-relator monoids, Extension of the decidability of the marked PCP to instances with unique blocks, The decision problem for some logics for finite words on infinite alphabets, Termination of \(\{aa\rightarrow bc,bb\rightarrow ac,cc\rightarrow ab\}\), On the termination problem for one-rule semi-Thue system, On the decidability of semigroup freeness, Undecidability of infinite post correspondence problem for instances of size 8, Improved matrix pair undecidability results, Weighted Automata on Infinite Words in the Context of Attacker-Defender Games, New proof for the undecidability of the circular PCP, Integer Weighted Automata on Infinite Words, Synchronizing deterministic push-down automata can be really hard, On the \(n\)-permutation Post correspondence problem, On undecidability bounds for matrix decision problems, Word problem for deterministic and reversible semi-Thue systems, Reachability problems in quaternion matrix and rotation semigroups, LARGE SIMPLE BINARY EQUALITY WORDS, On the size of computationally complete hybrid networks of evolutionary processors, Unnamed Item, UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, Tiling the Plane with a Fixed Number of Polyominoes, Rectangular tileability and complementary tileability are undecidable, Reachability problems in low-dimensional nondeterministic polynomial maps over integers, REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM, Post Correspondence Problem and Small Dimensional Matrices, Average-Case Completeness in Tag Systems, Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian, Undecidability of infinite post correspondence problem for instances of Size 9, Relative undecidability in term rewriting. II: The confluence hierarchy, Modelization of deterministic rational relations, Undecidable Properties on Length-Two String Rewriting Systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some undecidable termination problems for semi-Thue systems
- Investigations on algorithmic questions of algebra
- Termination of rewriting
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Examples of undecidable problems for 2-generator matrix semigroups
- Undecidable problems for probabilistic automata of fixed dimension
- A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
- Relative undecidability in term rewriting. I: The termination hierarchy
- GENERALIZED POST CORRESPONDENCE PROBLEM FOR MARKED MORPHISMS
- Decidability of Termination of Grid String Rewriting Rules
- One-rule semi-Thue systems with loops of length one, two or three
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
- Non-Looping String Rewriting
- Recursive Unsolvability of a problem of Thue
- Simulation of Turing machines by a left-linear rewrite rule
- On the termination problem for one-rule semi-Thue system
- The undecidability of the Turing machine immortality problem
- Word and conjugacy problems in groups with only a few defining relations
- Formal Reductions of the General Combinatorial Decision Problem
- Semi-Thue systems with an inhibitor
- Termination and derivational complexity of confluent one-rule string-rewriting systems
