patternMinor
What do queues and stacks correspond to in math?
Viewed 0 times
whatcorrespondstacksmathandqueues
Problem
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)
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)
Solution
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 describe the same class of languages. We also know that pushdown automata are like DFAs, only they also do stack operations. So 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 pop 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 an inner product space using Paul Dirac's bra-ket notation, as used in quantum mechanics.
(As an aside, 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, this use of stack operations (over a finite set of symbols) form an interesting algebra which was discovered in a completely different context. Other uses may not.
This alone answers your question with a resounding "it depends".
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 describe the same class of languages. We also know that pushdown automata are like DFAs, only they also do stack operations. So 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 pop 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 an inner product space using Paul Dirac's bra-ket notation, as used in quantum mechanics.
(As an aside, 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, this use of stack operations (over a finite set of symbols) form an interesting algebra which was discovered in a completely different context. Other uses may not.
This alone answers your question with a resounding "it depends".
Context
StackExchange Computer Science Q#29118, answer score: 9
Revisions (0)
No revisions yet.