Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Expressive completeness failure in branching time structures
Amir A. Journal of Computer and System Sciences34 (1):27-42,1987.Type:Article
Date Reviewed: Sep 1 1988

As we all know, all expressions in standard Boolean logic can be represented using only a finite number of different connectives. In fact, each expression is equivalent to an expression that only uses NANDs. Although standard logic has many applications in computer science, time-dependent logics seem to be needed to describe and express facts about concurrent processes. This paper cites previous results that show that if time can be a general ordered structure, then no finite number of connectives can suffice to represent all expressions, while if time is linearly ordered then a finite number of connectives do suffice. The paper shows that if time is an infinite discrete tree with an unbounded branching factor, then no finite number of connectives suffice. The proof depends on the fact that certain formulas in n variables are not equivalent to any expression with fewer variables and that this property can be maintained as one builds an infinite branching structure. The author conjectures that if the branching factor is bounded then a finite number of connectives suffice. For such an abstruse topic, this paper is rather easy to follow because the author has included explanations after many of the theorems and definitions.

Reviewer:  Paul Cull Review #: CR112358
Bookmark and Share
 
Computational Logic (F.4.1 ... )
 
 
Algebraic Language Theory (F.4.3 ... )
 
 
Computations On Discrete Structures (F.2.2 ... )
 
 
Reducibility And Completeness (F.1.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Computational Logic": Date
Extended Horn sets in propositional logic
Chandru V., Hooker J. Journal of the ACM 38(1): 205-221, 1991. Type: Article
Nov 1 1991
Preservation of expressive completeness in temporal models
Amir A., Gabbay D. (ed)   (,1991. Type: Proceedings
Oct 1 1987
Monotone versus positive
Ajtai M., Gurevich Y. (ed) Journal of the ACM 34(4): 1004-1015, 1987. Type: Article
Jul 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy