<p>If you have the algorithm, the Big O complexity can be calculated. What challenges are you facing?</p>
<p>There is a P-Complete O(n2) note here
<a href="https://www.sciencedirect.com/science/article/pii/S089054010300021X" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S089054010300021X</a></p>
<p>Is this what you are looking for?</p>

CC BY-SA 4.0
2024-05-02T11:38:08.277Z
Unfortunately that is not what I'm looking for as it relates to orientability/decision problems rather than the overall time complexity
Navvye
CC BY-SA 4.0
2024-04-29T02:17:35.690Z
2024-04-29T02:17:35.690Z
Sunny Armstrong
<p>I am currently studying the Knuth-Bendix completion algorithm and trying to understand the factors that contribute to its time complexity. This algorithm is used to transform a set of rewrite rules into a confluent rewrite system, ensuring that all derivable reductions of a term can be consistently reduced to a unique normal form if it exists. I know that the Knuth-Bendix completion Algorithm is a semi-decision algorithm, and that it may not always succeed.</p>
<p>I'd be very grateful if someone could demonstrate the time complexity of this algorithm in any specific case! Here's an example from Wikipedia using the shortlex order</p>
<p><span class="math-container">$$
\left\langle x, y \mid x^3=y^3=(x y)^3=1\right\rangle
$$</span></p>
<p>Thank you!</p>

CC BY-SA 4.0
2024-04-28T23:46:57.943Z
Cross-posted: https://cs.stackexchange.com/q/167849/755. Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
CC BY-SA 4.0
2024-04-29T01:36:37.280Z
@D.W. deleted from the CS stack exchange
Navvye
<cc.complexity-theory><fl.formal-languages><term-rewriting-systems>
Time Complexity of KnuthBendixCompletion Algorithm
Navvye
# Time Complexity of KnuthBendixCompletion Algorithm

(Asked by: username_0 on 2024-04-28)

I am currently studying the Knuth-Bendix completion algorithm and trying to understand the factors that contribute to its time complexity. This algorithm is used to transform a set of rewrite rules into a confluent rewrite system, ensuring that all derivable reductions of a term can be consistently reduced to a unique normal form if it exists. I know that the Knuth-Bendix completion Algorithm is a semi-decision algorithm, and that it may not always succeed.

I'd be very grateful if someone could demonstrate the time complexity of this algorithm in any specific case! Here's an example from Wikipedia using the shortlex order

$$
\left\langle x, y \mid x^3=y^3=(x y)^3=1\right\rangle
$$

Thank you!

**Tags:** cc.complexity-theory, fl.formal-languages, term-rewriting-systems
> **Comments:**
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/167849/755. Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  
> **username_0**: @D.W. deleted from the CS stack exchange  

---

## 1 answers

### Answer by username_2 on 2024-04-29. Score: -1

If you have the algorithm, the Big O complexity can be calculated. What challenges are you facing?

There is a P-Complete O(n2) note here
<https://www.sciencedirect.com/science/article/pii/S089054010300021X>

Is this what you are looking for?

> **Comments:**
> **username_0**: Unfortunately that is not what I'm looking for as it relates to orientability/decision problems rather than the overall time complexity  

---

