Makanin's algorithm is not primitive recursive
type: Item
instance of: scholarly article
title: Makanin's algorithm is not primitive recursive
zbMATH Open document ID: 0908.68107
DOI: 10.1016/S0304-3975(96)00321-0
author: Antoni Kościelski
author: Leszek Pacholski
published in: Theoretical Computer Science
publication date: 1998-08-13T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1189636
zbMATH Keywords: Makanin's decision procedure
zbMATH Keywords: equational satisfiability in semigroups
MaRDI profile type: Publication
cites work: Solving word equations
cites work: Investigations on algorithmic questions of algebra
cites work: Minimal and complete word unification
cites work: Q5607228
cites work: An analysis of Makanin's algorithm deciding solvability of equations in free groups
cites work: Complexity of Makanin's algorithm
cites work: Q5686240
cites work: THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
cites work: EQUATIONS IN A FREE GROUP
cites work: DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
cites work: Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre
cites work: Q5678447
cites work: ON SYSTEMS OF EQUATIONS IN A FREE GROUP
cites work: Word unification and transformation of generalized equations
full work available at URL: s0304-3975(96)00321-0
OpenAlex ID: W1969654785
description: scientific article; zbMATH DE number 1189636