Recursive unsolvability of a problem of Thue

DOI10.2307/2267170zbMATH Open1263.03030OpenAlexW2004459113MaRDI QIDQ4919632FDOQ4919632

Authors: Emil Leon Post 

Publication date: 15 May 2013

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2267170

Recommendations

• A variant of a recursively unsolvable problem
• On reduced thue systems
• Publication:4729772
• scientific article; zbMATH DE number 671957
• Word problem for deterministic and reversible semi-Thue systems

Mathematics Subject Classification ID

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

Cites Work

• Formal Reductions of the General Combinatorial Decision Problem
• A variant of a recursively unsolvable problem
• Recursively enumerable sets of positive integers and their decision problems
• An Unsolvable Problem of Elementary Number Theory

Cited In (only showing first 100 items - show all)

• Contraction of Dirac matrices via chord diagrams
• Undecidable questions related to Church-Rosser Thue systems
• Computing finite semigroups
• The word problem and the isomorphism problem for groups
• The word problem for cancellation semigroups with zero
• Word problems
• Symmetric space-bounded computation
• Formal model of internal measurement: Alternate changing between recursive definition and domain equation
• Alfred Tarski and undecidable theories
• The word and generator problems for lattices
• Computing homology using generalized Gröbner bases
• Closing the Circle: An Analysis of Emil Post's Early Work
• Algorithmically finite groups.
• Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras
• A variant of a recursively unsolvable problem
• Finding non-trivial elements and splittings in groups.
• Frontier between decidability and undecidability: A survey
• Decision problems for propositional linear logic
• A field guide to equational logic
• Decidable approximations of term rewriting systems
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• On the mathematical foundations of \textit{Syntactic structures}
• The computability, definability, and proof theory of Artinian rings
• Word problem for deterministic and reversible semi-Thue systems
• Relational lattices: from databases to universal algebra
• Composition-diamond lemma for associative conformal algebras.
• Computability and Recursion
• Historical evolution of the concept of homotopic paths
• UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
• Complexity of certain decision problems about congruential languages
• Model-theoretic and algorithmic questions in group theory
• Inverse monoids: decidability and complexity of algebraic questions.
• Gröbner-Shirshov bases and their calculation
• Introduction to reconfiguration
• Generic complexity of finitely presented monoids and semigroups
• Automaton semigroups
• Undecidability of existential properties in picture languages
• Implementing real numbers with RZ
• On regularity of context-free languages
• A strong geometric hyperbolicity property for directed graphs and monoids.
• Regular canonical systems
• The origins of combinatorics on words
• The theory of recursive functions, approaching its centennial
• On public key cryptosystem based on the word problem in a group
• The Complexity of Small Universal Turing Machines: A Survey
• Decision problems for semi-Thue systems with a few rules
• Well rewrite orderings and well quasi-orderings
• Undecidability of the identity problem for finite semigroups
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Process-centric views of data-driven business artifacts
• Turing oracle machines, online computing, and three displacements in computability theory
• Thickness of Feathers
• Word problems over traces which are solvable in linear time
• The word problem for semigroups with two generators
• Unsolvability of the universal theory of finite groups
• On the \(n\)-permutation Post correspondence problem
• All countable monoids embed into the monoid of the infinite random graph
• A Note on Pushdown Store Automata and Regular Systems
• Surprising areas in the quest for small universal devices
• On the descriptional complexity of the window size for deleting restarting automata
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Thue trees
• Complexity results on the conjugacy problem for monoids
• Polygraphs of finite derivation type
• On ground AC-completion
• Decidability and independence of conjugacy problems in finitely presented monoids
• New proof for the undecidability of the circular PCP
• A new lower bound construction for commutative Thue systems with applications
• Generic complexity of undecidable problems
• Monoïdes préordonnés et chaînes de Malcev
• On the decidability of semigroup freeness.
• The complexity of small universal Turing machines: A survey
• Combination techniques for non-disjoint equational theories
• Church-Rosser systems with respect to formal languages
• Formalization of the computational theory of a Turing complete functional language model
• Sur la liaison entre problèmes combinatoires et algorithmiques
• On complete one-way functions
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• An early completion algorithm: Thue's 1914 paper on the transformation of symbol sequences
• Martin Davis and Hilbert's tenth problem
• Why post did [not] have Turing's thesis
• The undecidability of the unrestricted modified edit distance
• Subexponentials in non-commutative linear logic
• The developments of the concept of machine computability from 1936 to the 1960s
• Generic complexity of the word problem in some semigroups
• Verifying polymer reaction networks using bisimulation
• Anisimov's theorem for inverse semigroups.
• Unsolvable algorithmic problems for semigroups, groups and rings
• The Bounded and Precise Word Problems for Presentations of Groups
• Hyperarithmetical Sets
• The word problem for \(1\mathcal{LC}\) congruences is NP-hard.
• Efficient Computation in Groups and Simplicial Complexes
• Finite Gröbner basis algebras with unsolvable nilpotency problem and zero divisors problem
• Generalized sums over histories for quantum gravity. II: Simplicial conifolds
• Nested sequents for intuitionistic modal logics via structural refinement
• Reconfiguration in bounded bandwidth and tree-depth
• Recursive undecidability of the binding property for finitely presented equational classes
• When Church-Rosser becomes context free
• The multiplicative-additive Lambek calculus with subexponential and bracket modalities
• The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups

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)