scientific article; zbMATH DE number 3920796

MaRDI QIDQ3697240zbMATH OpenFDO

Authors Michail R. Tetruashvili

Publication date 1984

zbMATH Keywords

computational complexityTuring machineword problem

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2112143
• scientific article; zbMATH DE number 1535398
• Isomorphism problem for semigroups with one defining relation
• Complexity of the word problem for commutative semigroups of fixed dimension
• scientific article; zbMATH DE number 1521041

Cited in

(6)

• McCammond’s normal forms for free aperiodic semigroups revisited
• scientific article; zbMATH DE number 4017191 (Why is no real title available?)
• scientific article; zbMATH DE number 2112143 (Why is no real title available?)
• Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
• On complexity of the word problem in semigroups with homogeneous relations
• Complexity of the word problem for commutative semigroups of fixed dimension

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3697240)