# Applications of Logic and Algebra in Computer Science

I have used logic for specification of security policies in a security model. One of my reviewers asked a question that "why did you use logic and not algebra for this purpose, and what is your justification?". The first answer that comes to my mind is that algebra is more suitable for using in modelling the behaviour (dynamic aspects). For example for specification of security protocols. However, logic is more suitable for specification of properties (static aspects). For example for specification of the security properties we require to satisfy in a computing environment, or the security properties we desire to be satisfied in a security protocol. In other words, algebra is suitable to say HOW, but logic is suitable to say WHAT.

My questions regarding this issue are:

1. Is my initial answer to this question correct or not?
2. What are the other answers for this question
3. What are the main references describing where we should use logic, and where we should use algebra in their applications in computer science?
-

I don't like this kind of question —not yours, your referee's— it's enough for authors to solve problems, the existence of other routes that other people might prefer is besides the point, unless there is some relative disadvantage that the referee can point out.

1. Is my initial answer to this question correct or not? — It's not what I would say. There are plenty of approaches to handle mutability in logic, of which dynamic logic is probably the most widely applied.
2. What are the other answers for this question? — I should think that in your shoes I would say something like: "The choice of logic vs. algebra is much less important than the design decisions made in formalising the specification. This is what seemed to me to be most well suited at the time."
3. What are the main references describing where we should use logic, and where we should use algebra in their applications in computer science? — I don't know of anything along the lines of what you are asking. Blackburn, de Rijke & Venema (2001) Modal Logic talks about the similarities and differences between algebraic and model-theoretic techniques - I left with the impression that the biggest issue was whether you preferred to work with completeness theorems or representation theorems.

To say something in addition to John's answer, here was a thread on Math Overflow, Is there a relationship between model theory and category theory, that I think gives some impression on how little distance there is seen to be between algebra and logic.

-
Yes, I think what the referee meant was "I would have used algebra, why didn't you?" Not a good question. – MikeC Oct 4 '10 at 16:51
I don't know anything about the context here, but: if this is an issue that readers will care about, then adding a sentence about it to the paper will make the paper stronger. So there are possible circumstances in which the referee's question is reasonable (e.g. if there are a lot of other papers that use algebra for similar things). On the other hand, if the referee is just pushing a personal preference, that's more unfortunate. – Carl Mummert Oct 5 '10 at 11:13
Thanks, I think I get my answer. – Morteza Amini Oct 7 '10 at 8:47

At some level, algebra and logic are equivalent. See Logic as Algebra by Paul Halmos and Steven Givant.

-
Yes, in particular Stone's representation theorem, which Halmos&Givant tackle in their chapter, Boolean universal algebra. – Charles Stewart Oct 4 '10 at 12:19

You may want to read about the Curry-Howard isomorphism which, for example, tells us that types in typed lambda calculus (thus in programming languages like OCaml, SML, Haskell, among others) actually are propositions in some logic formalism, and that values of these types are proofs of the corresponding propositions. It is e.g used to develop proof assistants that actually also are functional programming languages (Agda, Coq, Epigram, ...). Regarding algebra, you may want to read "Elements of Programming", by Alexander Stepanov.

-