Reductions and functors from problems to word problems
type: Item
instance of: scholarly article
title: Reductions and functors from problems to word problems
zbMATH Open document ID: 0947.68537
DOI: 10.1016/S0304-3975(98)00131-5
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
review text: We introduce reductions of problems to word problems of finitely generated semigroups and groups, with special properties. (1) Complexity properties: The reductions are computable in linear time, and they reduce problems to word problems with approximately the same time complexity. For groups, the constructions use small-cancellation theory. (2) Algebraic properties: We also associate semigroups and groups with reduction functions, in such a way that composition of reduction functions corresponds to the free product with amalgamation. Moreover, we make the reductions (from problems to word problems) functorial. For this, we reformulate problem classes as categories (e.g., NP can be viewed as the category whose objects are the languages in NP, and whose arrows are all polynomial-time one-to-one reductions).
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1454555
zbMATH Keywords: Word problem
zbMATH Keywords: Complexity
zbMATH Keywords: Reductions
zbMATH Keywords: Functors
author: J.-C. Birget
MaRDI profile type: Publication
cites work: Time/Space Trade-Offs for Reversible Computation
cites work: Q4430300
cites work: Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
cites work: Infinite string rewrite systems and complexity
cites work: Isoperimetric functions of groups and computational complexity of the word problem
cites work: Confluent and Other Types of Thue Systems
cites work: Dehn's Algorithm and the Complexity of Word Problems
cites work: Q5564342
cites work: Q4040880
cites work: Real-Time Simulation of Multihead Tape Units
cites work: Q4279731
cites work: Embedding Theorems with Amalgamation for Semigroups†
cites work: Q3862379
cites work: Q5586334
cites work: Q3998976
cites work: New Real-Time Simulations of Multihead Tape Units
cites work: Q4145882
cites work: Q4298260
cites work: Isoperimetric and isodiametric functions of groups
full work available at URL: s0304-3975(98)00131-5
OpenAlex ID: W1997172367
Recommended article: Q3680820
Recommended article: Foundations of Software Science and Computation Structures
Recommended article: Q3028369
Recommended article: On reduction theorems in the problem of composition of functions
Recommended article: Q3337523
Recommended article: Classifying word problems of finitely generated algebras via computable reducibility
Recommended article: Q4522249
Recommended article: Rudimentary reductions revisited
Recommended article: Q3326886
Recommended article: Reverse Mathematics
description: scientific article; zbMATH DE number 1454555