2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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 be suitable? $\endgroup$ Mar 18, 2023 at 17:53
  • $\begingroup$ 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. $\endgroup$ Mar 20, 2023 at 23:20
  • 1
    $\begingroup$ 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? $\endgroup$
    – usul
    Jul 31, 2023 at 17:52
  • $\begingroup$ 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. $\endgroup$ Aug 2, 2023 at 3:47
  • $\begingroup$ 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. $\endgroup$
    – usul
    Aug 2, 2023 at 4:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.