A geometric connection to threshold logic via cubical lattices
Tóm tắt
A cut-complex is a cubical complex whose vertices are strictly separable from the rest of the vertices of the n-cube by a hyperplane of R
n
. These objects render geometric presentations for threshold Boolean functions, the core objects of study in threshold logic. By applying cubical lattices and geometry of rotating hyperplanes, we prove necessary and sufficient conditions to recognize the cut-complexes with 2 or 3 maximal faces. This result confirms a positive answer to an old conjecture of Metropolis-Rota concerning cubical lattices.
Tài liệu tham khảo
Boros, E., Hammer, P. L., Ibaraki, T., & Kawakami, K. (1997). Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle. SIAM Journal on Computing, 26, 93–109.
Cepek, O., Kronus, D., & Kucera, P. (2006). Recognition of interval Boolean functions (Tech. Rep. 15-06). RUTCOR Research Report RRR, Rutgers University, New Brunswick, NJ. Accepted for publication in Annals of Mathematics and Artificial Intelligence.
Chen, W. Y. C., & Stanley, R. P. (1993). Derangements on the n-cube. Discrete Mathematics, 115, 65–75.
Ehrenborg, R., & Readdy, M. (1996). The r-cubical lattice and a generalization of the cd-index. European Journal of Combinatorics, 17, 709–725.
Elgot, C. C. (1960). Truth functions realizable by single threshold organs. In AIEE conf. paper, 60-1311 (Oct. 1960); also SCTLD (Sept. 1961) (pp. 225–245).
Emamy-K, M. R. (1986). On the cuts and cut-number of the 4-cube. Journal of Combinatorial Theory, Series A, 41(2), 221–227.
Emamy-K, M. R. (1988). On the covering cuts of C d, d≤5. Discrete Mathematics, 68, 191–196.
Emamy-K, M. R. (1999). Geometry of cut-complexes and threshold logic. Journal of Geometry, 65, 91–100.
Emamy-K, M. R. (2000). Elements of convex polytopes. UPR Lecture Notes.
Emamy-K, M. R. (2004). A new elementary proof for an old theorem on convex sets. Congressus Numerantium, 170, 107–112.
Davey, B. A., & Priestley, H. A. (2002). Introduction to lattice and order. Cambridge: Cambridge University Press.
Grünbaum, B. (1975). Polytopal graph. MAA Studies in Mathematics, 12, 201–224.
Grünbaum, B. (2003). In V. Kaibel, V. Klee, & G. M. Ziegler (Eds.), Convex polytopes. Berlin: Springer.
Hu, S.-T. (1965). Threshold logic. Berkeley: University of California Press.
Klee., V. (1999). Shapes of the future. Some unresolved problems in high-dimensional intuitive geometry. In Proceedings of the 11th Canadian conference on computational geometry (p. 17).
Metropolis, N., & Rota, G.-C. (1978a). On the lattice of faces of the n-cube. Bulletin of the American Mathematical Society, 84(2), 284–286.
Metropolis, N., & Rota, G.-C. (1978b). Combinatorial structure of the faces of the n-cube. SIAM Journal on Applied Mathematics, 35(4), 689–694.
Peled, U., & Simeone, B. (1994). A O(nm)-time algorithm for computing the dual of a regular Boolean function. Discrete Applied Mathematics, 49(1–3), 309–323.
Saks, M. E. (1993). Slicing the hypercube. In Surveys in combinatorics (pp. 211–255). Cambridge: Cambridge University Press.
Stanley, R. P. (2002). Enumerative combinatorics (Vol. 1). Cambridge: Cambridge University Press.
Sohler, C., & Ziegler, G. M. (2000). Computing cut numbers. In Proceedings of the 12th CCCG (p. 17).
Muroga, S. (1971). Threshold logic and its applications. Toronto: Wiley.
Winder, R. O. (1962). Threshold logic. PhD. dissertation, Math. Dept., Princeton University.
Ziegler, G. M. (1994). Lectures on polytopes. Berlin: Springer.
Ziegler, G. M. (2000). http://www.uni-paderborn.de/cs/cubecuts.