3
$\begingroup$

Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, ....

As abstract data types, what do queues and stacks correspond to in math? For example, some special paths in graph theory?

Have stacks and queues been treated mathematically and, if so, how are they usually treated within mathematic?

What mathematical concepts form the basis for stacks and queues?

Are there references that introduce data structures as models of monoids and other algebraic concepts? (Raphael said data structures are)

$\endgroup$
  • 1
    $\begingroup$ Do you have any reason to suspect that they correspond to anything? $\endgroup$ – David Richerby Aug 13 '14 at 19:49
  • 1
    $\begingroup$ In what sense does one "access" vertices in a path? $\endgroup$ – David Richerby Aug 13 '14 at 20:07
  • 1
    $\begingroup$ Considering a graph as an object of mathematics (not as an implementation of some data structure), you can enumerate the vertices in whatever order you please. And there's no such thing as "fetching attributes". $\endgroup$ – David Richerby Aug 13 '14 at 20:20
  • 1
    $\begingroup$ Sorry -- I'm not trying to be argumentative. Trying to find connections between datastructures and mathematical objects is fine and there are many such connections. You're proposing to connect the datastructure "queue" with the mathematical object "graph". Maybe that works; maybe it doesn't. But, when you talk about this, you talk about the graph itself as a datastructure (e.g., assuming there's a single, fixed enumeration of the vertices; "fetching" properties and so on), when you're supposed to be considering it as a mathematical object. $\endgroup$ – David Richerby Aug 13 '14 at 21:03
  • 1
    $\begingroup$ A queue is an enumeration/ordinality, but it's a potentially dynamic one...does that make it a math concept? I think they're a purely logical construct. Queues and Stacks are arbitrary ordering applied to a set. $\endgroup$ – InfernalRapture Aug 14 '14 at 1:25
6
$\begingroup$

As a practical matter, how you treat data structures mathematically largely depends what you're trying to do.

For example, suppose that you're trying to reason about the correctness of programs that use stacks and/or queues. In that situation, you'd want to treat the stack/queue as an abstract object, and axiomatise its properties. So you develop (say) a theory of stacks which can be layered on top of a general theorem prover.

You can do this quite straightforwardly in constructive type theories, such as the calculus of constructions. It's worth taking a look at the theories that come with Coq (the proof management system); it has a theory of strings, a theory of lists, a theory of maps, and so on.

Having said that, stacks and queues in some contexts do model mathematical objects. I'm going to run with the example of pushdown automata. In this case, the stack symbols are a fixed finite set (and they have no structure; it makes no sense to do maths on the stack symbol names themselves!), and so the stacks form an interesting algebra.

I'm going to start with regular languages, which we can axiomatise as a Kleene algebra. A Kleene algebra is an idempotent semiring plus the Kleene star operator. The two ring-like operations $\cdot$ and $+$ correspond to concatenation and set union, and $0$ and $1$ correspond to the null set and the empty string.

We know that DFAs and regular expressions are basically the same thing. We also know that pushdown automata are like DFAs, only they also do stack operations. There's no reason why we can't put stack operations in regular expressions; in this way, we could express context-free languages using a regular expression-like operation.

So let's do that. We'll denote a stack push of symbol $i$ using the notation $\left\langle i \right|$ and a pop using the notation $\left| i \right\rangle$. Now we need to work out how these stack operations work algebraically.

Terminal symbols commute with stack operations, in the sense that reading as symbol followed by a stack push or pop is the same as doing the stack operation followed by reading the symbol:

$$a \left\langle i \right| = \left\langle i \right| a$$ $$a \left| i \right\rangle = \left| i \right\rangle a $$

Finally, we need to work out what happens when two stack operations meet. A push of a symbol followed by a pop of the same symbol is equivalent to reading the empty string (i.e. doing nothing):

$$\left\langle i \right| \left| i \right\rangle = 1$$

However, pushing a symbol followed by trying to push a different symbol cannot happen. This is equivalent to the empty set (i.e. the language with no strings in it):

$$\left\langle i \right| \left| j \right\rangle = 0, \hbox{if}\,i \ne j$$

In other words, we're looking at something very like a vector space. Strings of terminals behave like scalars, and stack operations behave like vectors and one-forms. When a push meets a pop, they behave like an inner product where the basis vectors are orthonormal.

Moreover, if the stack is nonempty, then any pop followed by a push of the same symbol should be a no-op:

$$\left| 1 \right\rangle \left\langle 1 \right| + \left| 2 \right\rangle \left\langle 2 \right| + \cdots + \left| n \right\rangle \left\langle n \right| = 1$$

Using this algebra, we can (say) express $a^n b^n$ as $\left\langle 1 \right| (a \left\langle 2 \right|)^* (b \left| 2 \right\rangle)^* \left| 1 \right\rangle$. It's a little unwieldy, but it works.

Attentive readers might have caught on why I used this notation (lovingly stolen from Mark Hopkins): this is a Dirac algebra, as used in quantum mechanics.

It turns out that the analogy goes quite deep. A Turing machine can be thought of as an automaton with two stacks, and if you allow gradations between $0$ and $1$, you can axiomatise quantum Turing machines.

However, this is not the point I'm trying to get across. The point is that in this case, the stack operations form an interesting algebra which was discovered in a completely different context.

This alone answers your question with a resounding "it depends".

$\endgroup$
  • $\begingroup$ "We know that DFAs and regular expressions are basically the same thing." -- not at all, they are very different things (mathematically). If you assign fitting semantics to the objects they happen to describe the same class of languages, but that's not the same. Laboured analogy: a bicycle and rollerskates both get you from A to B but they are definitely not "basically the same thing". $\endgroup$ – Raphael Aug 14 '14 at 7:54
  • $\begingroup$ Very nice, thanks ... that is a compensation for all the boring stuff. - If you edit the text, please add some references (Dirac algebra is in wikipedia, Mark Hopkins, quantum TM ...) - - - - Minor bug: "pushing a symbol followed by trying to push a different symbol cannot happen" should be "... by trying to pop ...". $\endgroup$ – babou Aug 14 '14 at 7:56
  • $\begingroup$ @Raphael Isn't it the case that for any semantics S you assign to one, there is a semantics S' that you can assign the other, so that both will describe, differently, the same thing? $\endgroup$ – babou Aug 14 '14 at 11:44
  • $\begingroup$ Thanks for the comments. I'll be editing it when I have a chance. (One nit is that "Dirac algebra" means something slightly different; Hopkins incorrectly called it a "spinor algebra" which is something different again.) $\endgroup$ – Pseudonym Aug 14 '14 at 13:39
  • $\begingroup$ The first and last sentences summarize this pretty nicely, I think they deserve some bold text! ;-) $\endgroup$ – Nobbynob Littlun Aug 16 '14 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.