Recursive Unsolvability of a problem of Thue
From MaRDI portal
Publication:4919632
DOI10.2307/2267170zbMath1263.03030MaRDI 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
UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS, Conceptual Confluence in 1936: Post and Turing, Implementing Real Numbers With RZ, Solving the Conjugacy Decision Problem via Machine Learning, Surprising Areas in the Quest for Small Universal Devices, Gröbner–Shirshov bases and their calculation, Combination techniques for non-disjoint equational theories, Subexponentials in non-commutative linear logic, Anisimov's Theorem for inverse semigroups, The Developments of the Concept of Machine Computability from 1936 to the 1960s, The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes, Regular canonical systems, ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA, DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS, Thickness of Feathers, The equivalence of some general combinatorial decision problems, The many-one equivalence of some general combinatorial decision problems, A Note on Pushdown Store Automata and Regular Systems, Computability and Recursion, Rigidity is undecidable, The word problem for semigroups with two generators, Monoïdes préordonnés et chaînes de Malcev, Relational lattices: from databases to universal algebra, New proof for the undecidability of the circular PCP, Computing homology using generalized Gröbner bases, Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras, On the mathematical foundations of \textit{Syntactic structures}, Generic complexity of finitely presented monoids and semigroups, On the \(n\)-permutation Post correspondence problem, Algorithmically finite groups., Finding non-trivial elements and splittings in groups., On complete one-way functions, A strong geometric hyperbolicity property for directed graphs and monoids., On regularity of context-free languages, Conjugacy in monoids with a special Church-Rosser presentation is decidable, A new lower bound construction for commutative Thue systems with applications, The origins of combinatorics on words, Word problems over traces which are solvable in linear time, All countable monoids embed into the monoid of the infinite random graph, 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, 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., 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, Polygraphs of finite derivation type, 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, The word problem for cancellation semigroups with zero, Alfred Tarski and undecidable theories, Unnamed Item, Efficient Computation in Groups and Simplicial Complexes, Church-Rosser systems with respect to formal languages, 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
Cites Work
