On the complexity of theories of permutations
type: Item
instance of: scholarly article
title: On the complexity of theories of permutations
zbMATH Open document ID: 0613.03002
DOI: 10.1016/0304-3975(85)90074-X
author: Elisabeth Pelz
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: The first-order theory T of two permutations which commute is investigated and its decidability is proved. Moreover, we show that the computational complexity of the decision algorithm for SAT(T) - on NTM's and ATM's - is the same (for upper and lower bounds) as that of the theory of one permutation.
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 3991472
zbMATH Keywords: two commuting permutations
zbMATH Keywords: first-order theory
zbMATH Keywords: computational complexity
zbMATH Keywords: decision algorithm
MaRDI profile type: Publication
cites work: The complexity of logical theories
cites work: Alternation
cites work: Q3220545
cites work: The computational complexity of logical theories
cites work: Q5551141
cites work: Q5592246
cites work: Q3887443
cites work: Q5646891
cites work: Q5586197
cites work: Q3888985
full work available at URL: 0304-3975(85)90074-x
OpenAlex ID: W1990024032
description: scientific article; zbMATH DE number 3991472