On the Inversion Complexity of a System of Functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Inversion Complexity of a System of Functions

Full text

Pdf (131 KB)

Source

Journal of the ACM (JACM) archive
Volume 5 , Issue 4 (October 1958) table of contents

Pages: 331 - 334

Year of Publication: 1958

ISSN:0004-5411

Author

A. A. Markov

V. Steklov Mathematical Institute, Akad. Nauk SSSR

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 35, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/320941.320945 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. C. KLiEN~: Introductior~ to metamathematics. 1957.
	2	E. N. GILBERT: jr. Math. Phys. 33, 57 (1954).

CITED BY 9

	Robert Beals , Tetsuro Nishino , Keisuke Tanaka, More on the complexity of negation-limited circuits, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.585-595, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Kazuyuki Amano , Akira Maruoka , Jun Tarui, On the negation-limited circuit complexity of merging, Discrete Applied Mathematics, v.126 n.1, p.3-8, March 2003
	Shao Chin Sung , Keisuke Tanaka, Limiting negations in bounded-depth circuits: an extension of Markov's theorem, Information Processing Letters, v.90 n.1, p.15-20, 15 April 2004
	Stasys Jukna, On the minimum number of negations leading to super-polynomial savings, Information Processing Letters, v.89 n.2, p.71-74, 31 January 2004
	Keisuke Tanaka , Tetsuro Nishino, On the complexity of negation-limited Boolean networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.38-47, May 23-25, 1994, Montreal, Quebec, Canada
	Tao Feng , Li-C Wang , Kwang-Ting (Tim) Cheng , Chih-Chang (Andy) Lin, Using 2-domain partitioned OBDD data structure in an enhanced symbolic simulator, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.4, p.627-650, October 2005
	Hiroki Morizumi , Jun Tarui, Linear-size log-depth negation-limited inverter for k-tonic binary sequences, Theoretical Computer Science, v.410 n.11, p.1054-1060, March, 2009
	Hiroki Morizumi, Note: Limiting negations in non-deterministic circuits, Theoretical Computer Science, v.410 n.38-40, p.3988-3994, September, 2009
	J. Paul Roth, Minimization over Boolean trees, IBM Journal of Research and Development, v.4 n.5, p.543-558, November 1960