<p>I'm asking this question from a fairly naive position, so apologies in advance, etc.</p>
<p>I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested in is expressing union, intersection, subset, superset, etc of the output of algorithms.</p>
<p>Simplest example: Euclid's algorithm is a subset of Extended Euclid's algorithm, because the former returns <span class="math-container">$\{GCD(a, b)\}$</span> where the latter returns <span class="math-container">$\{GCD(a, b), BI(a, b)\}$</span>. (Where BI stands for the coefficients of Bézout's Identity.)</p>
<p>Take A* and Dijkstra's algorithm: they both compute the shortest path from a source node to a goal node; Dijkstra's algorithm also computes the shortest path from the source to every other node, A* computes an open and closed set; so the intersection of their outputs is definitely non-empty, but is A* a subset of Dijkstra? I presume it is not, because the open/closed sets at least have heuristic information not computed by Dijkstra, but I'm not 100% certain.</p>
<p>For argument's sake, you might say that linear search and binary search (as defined in Knuth) over the input space that is valid to both of them (i.e. sorted sequences), have a non-empty intersection: if the value searched for is unique or not present, they return the same result, but when the value is present and not unique then sometimes they won't return the same result. So they have a non-empty intersection and neither is a subset of the other.</p>
<p>The relations can be expressed in set theory, so I guess my question is, does a calculus or formalism exist for determining the relations? Is there any research in this vein? I have looked in vain because I don't know the right terms to search for.</p>

CC BY-SA 4.0
2023-03-18T17:53:08.200Z
I'm not sure I fully understand what you mean: union, intersection, subset, etc  correspond quite closely to  disjunction, conjunction, implication etc, and the axioms of set theory and similar foundations of mathematics are in parts about infinite collections, which no algorithm can produce in finite time. Since you mention Bird–Meertens, would a formalism like [higher-order  simple predicate logic](https://en.wikipedia.org/wiki/Higher-order_logic) be suitable?
Martin Berger
CC BY-SA 4.0
2023-03-20T23:20:20.883Z
Thanks for your comment. I don't think there is any concern about infinite collections because the sets I'm talking about are the set of objects/values returned by an algorithm, which are finite in size, although could be parameterized by the size of the input, i.e. an algorithm that operates on input of size n produces output of size n, or log n, etc.
Jeremy W. Murphy
CC BY-SA 4.0
2023-07-31T17:52:44.420Z
Interesting. I haven't seen discussion of this idea in theoretical CS, which focuses mainly on correctness, e.g. binary search and linear search are both "correct". It might also discuss when one algorithm's output can be deduced from another's, i.e. reductions. On the other hand, programming languages theory will often talk about the type of the output, but I don't think it would capture that binary and linear search, although they have the same type signature and are both "correct", can return different objects. Overall, I'm wondering if there's a particular motivation for the question?
usul
CC BY-SA 4.0
2023-08-02T03:47:19.690Z
Thanks, @usul Do you think then that this topic fits within TCS, or does it belong elsewhere? The motivation is a line of research that I'm exploring, which is a bit hard to explain, but I'm looking at how to determine when you've found an algorithm that is a superset of all related algorithms.
"Related" meaning they take the same input, have the same efficiency (for some definition of "efficiency") and return some fundamental thing in common.
Jeremy W. Murphy
CC BY-SA 4.0
2023-08-02T04:48:58.653Z
Sounds like TCS would be the right home! But not sure if programming languages, or some branch of complexity theory, or if it just hasn't been studied.
usul
<ds.algorithms>
Is there a calculus or formalism for measuring set relations between algorithm outputs?
Jeremy W. Murphy
# Is there a calculus or formalism for measuring set relations between algorithm outputs?

(Asked by: username_0 on 2023-03-18)

I'm asking this question from a fairly naive position, so apologies in advance, etc.

I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested in is expressing union, intersection, subset, superset, etc of the output of algorithms.

Simplest example: Euclid's algorithm is a subset of Extended Euclid's algorithm, because the former returns $\{GCD(a, b)\}$ where the latter returns $\{GCD(a, b), BI(a, b)\}$. (Where BI stands for the coefficients of Bézout's Identity.)

Take A\* and Dijkstra's algorithm: they both compute the shortest path from a source node to a goal node; Dijkstra's algorithm also computes the shortest path from the source to every other node, A\* computes an open and closed set; so the intersection of their outputs is definitely non-empty, but is A\* a subset of Dijkstra? I presume it is not, because the open/closed sets at least have heuristic information not computed by Dijkstra, but I'm not 100% certain.

For argument's sake, you might say that linear search and binary search (as defined in Knuth) over the input space that is valid to both of them (i.e. sorted sequences), have a non-empty intersection: if the value searched for is unique or not present, they return the same result, but when the value is present and not unique then sometimes they won't return the same result. So they have a non-empty intersection and neither is a subset of the other.

The relations can be expressed in set theory, so I guess my question is, does a calculus or formalism exist for determining the relations? Is there any research in this vein? I have looked in vain because I don't know the right terms to search for.

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: I'm not sure I fully understand what you mean: union, intersection, subset, etc  correspond quite closely to  disjunction, conjunction, implication etc, and the axioms of set theory and similar foundations of mathematics are in parts about infinite collections, which no algorithm can produce in finite time. Since you mention Bird–Meertens, would a formalism like [higher-order  simple predicate logic](https://en.wikipedia.org/wiki/Higher-order_logic) be suitable?  
> **username_0**: Thanks for your comment. I don't think there is any concern about infinite collections because the sets I'm talking about are the set of objects/values returned by an algorithm, which are finite in size, although could be parameterized by the size of the input, i.e. an algorithm that operates on input of size n produces output of size n, or log n, etc.  
> **username_2**: Interesting. I haven't seen discussion of this idea in theoretical CS, which focuses mainly on correctness, e.g. binary search and linear search are both "correct". It might also discuss when one algorithm's output can be deduced from another's, i.e. reductions. On the other hand, programming languages theory will often talk about the type of the output, but I don't think it would capture that binary and linear search, although they have the same type signature and are both "correct", can return different objects. Overall, I'm wondering if there's a particular motivation for the question?  
> **username_0**: Thanks, @usul Do you think then that this topic fits within TCS, or does it belong elsewhere? The motivation is a line of research that I'm exploring, which is a bit hard to explain, but I'm looking at how to determine when you've found an algorithm that is a superset of all related algorithms. "Related" meaning they take the same input, have the same efficiency (for some definition of "efficiency") and return some fundamental thing in common.  
> **username_2**: Sounds like TCS would be the right home! But not sure if programming languages, or some branch of complexity theory, or if it just hasn't been studied.  

---

## 0 answers

