Recursive Unsolvability of a problem of Thue
From MaRDI portal
Publication:4919632
DOI10.2307/2267170zbMath1263.03030OpenAlexW2004459113MaRDI QIDQ4919632
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
Related Items (only showing first 100 items - show all)
Contraction of Dirac matrices via chord diagrams ⋮ On termination of one rule rewrite systems ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ Complexity of certain decision problems about congruential languages ⋮ On public key cryptosystem based on the word problem in a group ⋮ The computability, definability, and proof theory of Artinian rings ⋮ The word problem for cancellation semigroups with zero ⋮ A Lyndon's identity theorem for one-relator monoids ⋮ Relational lattices: from databases to universal algebra ⋮ Decidability and independence of conjugacy problems in finitely presented monoids ⋮ Nested sequents for intuitionistic modal logics via structural refinement ⋮ An equational logic sampler ⋮ On ground AC-completion ⋮ On some algorithmic problems for groups and monoids ⋮ Decidable approximations of term rewriting systems ⋮ On the decidability of semigroup freeness ⋮ Finite Gröbner basis algebras with unsolvable nilpotency problem and zero divisors problem ⋮ On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata ⋮ The word and generator problems for lattices ⋮ Inverse monoids: decidability and complexity of algebraic questions. ⋮ Process-centric views of data-driven business artifacts ⋮ Unsolvable algorithmic problems for semigroups, groups and rings ⋮ Formal model of internal measurement: Alternate changing between recursive definition and domain equation ⋮ Undecidability of the identity problem for finite semigroups ⋮ The origins of combinatorics on words ⋮ New proof for the undecidability of the circular PCP ⋮ Left-divisibility and word problems in single relation monoids ⋮ Computing homology using generalized Gröbner bases ⋮ Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras ⋮ The undecidability of the unrestricted modified edit distance ⋮ Alfred Tarski and undecidable theories ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Unnamed Item ⋮ Computational complexity of the word problem in modal and Heyting algebras with a small number of generators ⋮ Generic complexity of undecidable problems ⋮ Recursive undecidability of the binding property for finitely presented equational classes ⋮ Efficient Computation in Groups and Simplicial Complexes ⋮ Sur la liaison entre problèmes combinatoires et algorithmiques ⋮ On the mathematical foundations of \textit{Syntactic structures} ⋮ Algorithmically finite groups. ⋮ Word problems over traces which are solvable in linear time ⋮ Generic complexity of finitely presented monoids and semigroups ⋮ Symmetric space-bounded computation ⋮ Church-Rosser systems with respect to formal languages ⋮ The word problem for \(1\mathcal{LC}\) congruences is NP-hard. ⋮ Composition-diamond lemma for associative conformal algebras. ⋮ Generalized sums over histories for quantum gravity. II: Simplicial conifolds ⋮ From Analytical Mechanics Problems to Rewriting Theory Through M. Janet’s Work ⋮ Conceptual Confluence in 1936: Post and Turing ⋮ On the \(n\)-permutation Post correspondence problem ⋮ Martin Davis and Hilbert’s Tenth Problem ⋮ Hyperarithmetical Sets ⋮ Why Post Did [Not Have Turing’s Thesis] ⋮ The word problem for one-relation monoids: a survey ⋮ Decision problems for propositional linear logic ⋮ Word problem for deterministic and reversible semi-Thue systems ⋮ A field guide to equational logic ⋮ All countable monoids embed into the monoid of the infinite random graph ⋮ Computing finite semigroups ⋮ Implementing Real Numbers With RZ ⋮ Historical evolution of the concept of homotopic paths ⋮ Verifying polymer reaction networks using bisimulation ⋮ Well rewrite orderings and well quasi-orderings ⋮ Decision problems for semi-Thue systems with a few rules ⋮ Finding non-trivial elements and splittings in groups. ⋮ Distributive lattices of subspaces and the equality problem for algebras with a single relation ⋮ The multiplicative-additive Lambek calculus with subexponential and bracket modalities ⋮ Word problems ⋮ On complete one-way functions ⋮ The complexity of small universal Turing machines: A survey ⋮ Solving the Conjugacy Decision Problem via Machine Learning ⋮ The origins of the halting problem ⋮ A strong geometric hyperbolicity property for directed graphs and monoids. ⋮ The undecidability of the elementary theory of lattices of all equational theories of large signature ⋮ On regularity of context-free languages ⋮ DECISION PROBLEMS FOR FINITELY PRESENTED AND ONE-RELATION SEMIGROUPS AND MONOIDS ⋮ Surprising Areas in the Quest for Small Universal Devices ⋮ WHEN CHURCH-ROSSER BECOMES CONTEXT FREE ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ Automaton semigroups ⋮ Frontier between decidability and undecidability: A survey ⋮ Undecidability of existential properties in picture languages ⋮ The complexity of the word problems for commutative semigroups and polynomial ideals ⋮ Undecidable questions related to Church-Rosser Thue systems ⋮ Introduction to reconfiguration ⋮ Many-one degrees associated with semi-Thue systems ⋮ Unsolvability of the universal theory of finite groups ⋮ Closing the Circle: An Analysis of Emil Post's Early Work ⋮ Polygraphs of finite derivation type ⋮ The word problem and the isomorphism problem for groups ⋮ Conjugacy in monoids with a special Church-Rosser presentation is decidable ⋮ Undecidability of Algebras of Binary Relations ⋮ Formalization of the computational theory of a Turing complete functional language model ⋮ The theory of recursive functions, approaching its centennial ⋮ Model-theoretic and algorithmic questions in group theory ⋮ Thue trees ⋮ Unsolvability of problems of equality and divisibility in certain varieties of semigroups ⋮ A new lower bound construction for commutative Thue systems with applications ⋮ UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS ⋮ Complexity results on the conjugacy problem for monoids
Cites Work
This page was built for publication: Recursive Unsolvability of a problem of Thue
