Recursive unsolvability of a problem of Thue
From MaRDI portal
Recommendations
Cites work
Cited in
(only showing first 100 items - show all)- The complexity of small universal Turing machines: A survey
- Turing oracle machines, online computing, and three displacements in computability theory
- Automaton semigroups
- Unsolvability of the universal theory of finite groups
- Model-theoretic and algorithmic questions in group theory
- Unsolvability of problems of equality and divisibility in certain varieties of semigroups
- Complexity results on the conjugacy problem for monoids
- Complexity of certain decision problems about congruential languages
- The word and generator problems for lattices
- Unsolvable algorithmic problems for semigroups, groups and rings
- Recursive undecidability of the binding property for finitely presented equational classes
- Sur la liaison entre problèmes combinatoires et algorithmiques
- Symmetric space-bounded computation
- Decision problems for propositional linear logic
- A field guide to equational logic
- Historical evolution of the concept of homotopic paths
- Well rewrite orderings and well quasi-orderings
- Distributive lattices of subspaces and the equality problem for algebras with a single relation
- On termination of one rule rewrite systems
- Formal model of internal measurement: Alternate changing between recursive definition and domain equation
- The undecidability of the unrestricted modified edit distance
- The word problem for \(1\mathcal{LC}\) congruences is NP-hard.
- Composition-diamond lemma for associative conformal algebras.
- Frontier between decidability and undecidability: A survey
- Undecidability of existential properties in picture languages
- The computability, definability, and proof theory of Artinian rings
- Decidability and independence of conjugacy problems in finitely presented monoids
- Finite Gröbner basis algebras with unsolvable nilpotency problem and zero divisors problem
- Reconfiguration in bounded bandwidth and tree-depth
- Computing finite semigroups
- Decision problems for semi-Thue systems with a few rules
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Undecidable questions related to Church-Rosser Thue systems
- Many-one degrees associated with semi-Thue systems
- Thue trees
- Left-divisibility and word problems in single relation monoids
- Generalized sums over histories for quantum gravity. II: Simplicial conifolds
- The word problem for one-relation monoids: a survey
- Verifying polymer reaction networks using bisimulation
- The multiplicative-additive Lambek calculus with subexponential and bracket modalities
- The origins of the halting problem
- Formalization of the computational theory of a Turing complete functional language model
- A Lyndon's identity theorem for one-relator monoids
- Nested sequents for intuitionistic modal logics via structural refinement
- Word problem for deterministic and reversible semi-Thue systems
- The undecidability of the elementary theory of lattices of all equational theories of large signature
- Introduction to reconfiguration
- Process-centric views of data-driven business artifacts
- Inverse monoids: decidability and complexity of algebraic questions.
- Computational complexity of the word problem in modal and Heyting algebras with a small number of generators
- The Complexity of Small Universal Turing Machines: A Survey
- On the decidability of semigroup freeness.
- On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
- Relational lattices: from databases to universal algebra
- Polygraphs of finite derivation type
- From Analytical Mechanics Problems to Rewriting Theory Through M. Janet’s Work
- Martin Davis and Hilbert's tenth problem
- Hyperarithmetical Sets
- Why post did [not] have Turing's thesis
- When Church-Rosser becomes context free
- Closing the Circle: An Analysis of Emil Post's Early Work
- Generic complexity of undecidable problems
- DECISION PROBLEMS FOR FINITELY PRESENTED AND ONE-RELATION SEMIGROUPS AND MONOIDS
- Efficient Computation in Groups and Simplicial Complexes
- The word problem for cancellation semigroups with zero
- Alfred Tarski and undecidable theories
- New proof for the undecidability of the circular PCP
- Church-Rosser systems with respect to formal languages
- Computing homology using generalized Gröbner bases
- scientific article; zbMATH DE number 3690734 (Why is no real title available?)
- Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras
- The word problem and the isomorphism problem for groups
- The theory of recursive functions, approaching its centennial
- Undecidability of the identity problem for finite semigroups
- Word problems
- On the mathematical foundations of \textit{Syntactic structures}
- Generic complexity of finitely presented monoids and semigroups
- UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
- Conceptual Confluence in 1936: Post and Turing
- TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
- Implementing real numbers with RZ
- Solving the conjugacy decision problem via machine learning
- On the \(n\)-permutation Post correspondence problem
- Surprising areas in the quest for small universal devices
- Undecidability of Algebras of Binary Relations
- On public key cryptosystem based on the word problem in a group
- An equational logic sampler
- On ground AC-completion
- On some algorithmic problems for groups and monoids
- Decidable approximations of term rewriting systems
- On polynomial ideals, their complexity, and applications
- The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups
- The Bounded and Precise Word Problems for Presentations of Groups
- The B B Newman spelling theorem
- What's decidable about program verification modulo axioms?
- Residuated Algebraic Structures in the Vicinity of Pre-rough Algebra and Decidability
- Gröbner-Shirshov bases and their calculation
- An early completion algorithm: Thue's 1914 paper on the transformation of symbol sequences
- Combination techniques for non-disjoint equational theories
- Subexponentials in non-commutative linear logic
This page was built for publication: Recursive unsolvability of a problem of Thue
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4919632)
