Complex Algebras of Arithmetic

• Autorzy: Düntsch I. , Pratt–Hartmann I.
• Języki publikacji: EN

Abstrakty

EN

An arithmetic circuit is a labeled, acyclic directed graph specifying a sequence of arithmetic, and logical operations to be performed on sets of natural numbers. Arithmetic circuits can, also be viewed as the elements of the smallest subalgebra of the complex algebra of the semiring of, natural numbers. In the present paper we investigate the algebraic structure of complex algebras of, natural numbers and make some observations regarding the complexity of various theories of such algebras.

Słowa kluczowe

EN

arithmetic circuits

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 97, nr 4
• Strony: 347--367
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Düntsch I.

autor

Pratt–Hartmann I.

• Department of Computer Science, Brock University, St. Catharines, ON, L2S 3A1, Canada,

Bibliografia

• [1] Baker, K. A. (1977). Finite equational bases for finite algebras in a congruence-distributive equational class. Advances in Mathematics, 24(3):207-243.
• [2] Bayasgalan, B. (1988). Decidability of theories of derived structures of semigroups. Algebraic Systems and their Varieties, Ural. Gos. Univ. Sverdlovsk, pages 4-13. In Russian.
• [3] Birkhoff, G. (1935). On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society, 31:433-454.
• [4] Burris, S. and Sankappanavar, H. P. (1981). A Course in Universal Algebra. Springer-Verlag, New York.
• [5] Glaßer, C., Reitwießner, C., Travers, S. D., and Waldherr, M. (2007). Satisfiability of algebraic circuits over sets of natural numbers. In Arvind, V. and Prasad, S., editors, Foundations of Software Technology and Theoretical Computer Science, 27th International Conference (FSTTCS 2007), New Delhi, India, December 12-14, Proceedings, volume 4855 of Lecture Notes in Computer Science, pages 253-264. Springer.
• [6] Goldblatt, R. (1989). Varieties of complex algebras. Annals of Pure and Applied Logic, 44:173-242.
• [7] Jeż, A. and Okhotin, A. (2008). On the computational completeness of equations over sets of natural numbers. In Aceto, L., Damgard, I., Halldórsson, L. G. M., Ingólfsdóttir, A., and Walukiewicz, I., editors, Proceedings of ICALP 2008, Part II, volume 5126 of LNCS, pages 63-74. Springer.
• [8] Jipsen, P. (1992). Computer aided investigations of relation algebras. PhD thesis, Vanderbilt University.
• [9] Jónsson, B. and Tarski, A. (1951). Boolean algebras with operators I. American Journal of Mathematics, 73:891-939.
• [10] Koppelberg, S. (1989). General Theory of Boolean Algebras, volume 1 of Handbook on Boolean Algebras. North-Holland.
• [11] McKenzie, P. and Wagner, K. W. (2003). The complexity of membership problems for circuits over sets of natural numbers. In Alt, H. and Habib, M., editors, STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, volume 2607 of Lecture Notes in Computer Science, pages 571-582. Springer-Verlag.
• [12] McKenzie, P. and Wagner, K. W. (2007). The complexity of membership problems for circuits over sets of natural numbers. Computational Complexity, 16(3):211-244.
• [13] Okhotin, A. (2001). Conjunctive grammars. Journal of Automata, Languages and Combinatorics, 4:519-535.
• [14] Okhotin, A. (2003). Decision problems for language equations with boolean operations. In Baeten, J. C. M., Lenstra, J. K., Parrow, J., and Woeginger, G. J., editors, ICALP, volume 2719 of Lecture Notes in Computer Science, pages 239-251. Springer.
• [15] Pinus, A. G. and Vazhenin, Y. M. (2005). Elementary classification and decidability of theories of derived structures. Russian Math. Surveys, 60:395-432.
• [16] Pratt-Hartmann, I. and Düntsch, I. (2009). Functions definable by arithmetic circuits. In Ambos-Spies, K., Löwe, B., and Merkle, W., editors, Mathematical Theory and Computational Practice: 5th Conference on Computability in Europe, CiE 2009, volume 5635 of Lecture Notes in Computer Science, pages 409-418, Heidelberg. Springer Verlag.
• [17] Reich, P. (1996). Complex algebras of semigroups. PhD thesis, Iowa State University, Ames.