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, Implementing Real Numbers With RZ, 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, The word problem for semigroups with two generators, Monoïdes préordonnés et chaînes de Malcev, 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, 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, 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, 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, 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
