article

Free access

Chow Parameters in Threshold Logic

Author:

Robert O. WinderAuthors Info & Claims

Journal of the ACM (JACM), Volume 18, Issue 2

Pages 265 - 289

https://doi.org/10.1145/321637.321647

Published: 01 April 1971 Publication History

PDF eReader

References

[1]

CHow, C. K. On the characterization of threshold functions. In Switching Circuit Theory and Logical Design, IEEE Special Publication S-134 (Sep. 1961), 34-38.

Google Scholar

[2]

COLEMAN, R .P . Orthogonal functions for the logical design of switching circuits. IRE Trans. EC10 (Sep. 1961), 379-383.

Google Scholar

[3]

DERTOUZOS, M. L. An approach to single threshold element synthesis. IEEE Trans. EC18 (Oct. 1964), 519-528; {Erratum: IEEE Trans. EC14 (Apr. 1965), 247}.

Google Scholar

[4]

DERTOUZOS, M.L. Threshold-element synthesis. Ph.D. Diss., Dep. of Elec. Eng., MIT, Cambridge, Mass. (June 1964).

Google Scholar

[5]

DERTOUZOS, M. L. Threshold Logic: A Synthesis Approach, MIT Press, Cambridge, Mass., 1965

Google Scholar

[6]

GABELMAN, I .J . The functional behavior of majority (threshold) elements. Ph.D. Diss., Dep. of Elec. Eng., Syracuse U., Syracuse, N.Y. (June 1961).

Google Scholar

[7]

GOLOMB, S. W. On the classification of Boolean functions. IRE Trans. CT6 (Suppl.) (May 1959), 176-186.

Google Scholar

[8]

GoTo, E. AND TAKAHASI, H. Some theorems useful in threshold logic for enumerating Boolean functions. In Information Processing 62, North Holland, Amsterdam, 1963, pp. 747-752; or Threshold, majority and bilateral switching devices. In Switching Theory in Space Technology, Stanford Univ. Press, 1963, pp. 47-67.

Google Scholar

[9]

HAWKINS, J. K. Self-organizing systems--A review and commentary. Proc. IRE le9 (Jan. 1961), 31-48.

Google Scholar

[10]

Hu, SzE-TsEN. Threshold Logic. U. of Cal. Press, Berkeley, Cal., 1965.

Google Scholar

[11]

KAPLAN, K. R. AND WINDER, R.O. Chebyshev approximation and threshold functions. IEEE Trans. EC14 (Apr. 1965), 250-252.

Google Scholar

[12]

KASZERMAN, P. On the synthesis of threshold devices. Ph.D. Diss., Dep. of Elee. Eng., New York U., New York (Sep. 1963).

Google Scholar

[13]

KASZERMAN, P. A geometric test-synthesis procedure for a threshold device. Inform. Control 6, 10 (Dec. 1963), 381-398.

Google Scholar

[14]

LEVINE, E. On the characterizing parameters of a threshold function. IEEE Trans. C17, (July 1968), 696-697.

Google Scholar

[15]

LIU, MING-TsAu. The triquare map method for realization of threshold functions. Ph.D. Diss., Dep. of Elec. Eng., U. of Pennsylvania (June 1964).

Google Scholar

[16]

MUROGA, S., TODA, I., AND TAKASU, S. Theory of majority decision elements. JFI 271 (May 1961), 376-418.

Google Scholar

[17]

NINOMIYA, ICHIZO. A study of the structures of Boolean functions and its application to the synthesis of switching circuits. Mere. Faculty Eng. (Nagoya U.) 13, 2 (Nov. 1961), 149-363.

Google Scholar

[18]

WINDER, R.O. Threshold logic. Ph.D. Diss., Dep. of Math, Princeton U. (May 1962).

Google Scholar

[19]

WINDER, R. O. Threshold logic in artificial intelligence. In Artificial Intelligence, IEEE Publication S-142 (Jan. 1963), 107-128.

Google Scholar

[20]

WINDER, R.O. Properties of threshold functions. IEEE Trans. EC14 (Apr. 1965), 252- 254.

Google Scholar

[21]

WINDER, R.O. Enumeration of seven-argument threshold functions. IEEE Trans. EC14 (June 1965), 315-325.

Google Scholar

[22]

WINDER, R.O. Threshold functions through n = 7. Scientific Report No. 7 for AFCRL on contract with RCA Laboratories, AF 19 "(604)8423, available through DDC and the IEEE Computer group repository, October 1964.

Google Scholar

[23]

WINDER, R.O. Symmetry types in threshold logic. IEEE Trans. C17 (Jan. 1968), 75-78.

Google Scholar

[24]

WINDER, R.O. Threshold gate approximations based on Chow parameters. IEEE Trans. C18 (Apr. 1969), 372-375.

Google Scholar

[25]

WINDER, R.O. Threshold logic asymptotes. IEEE Trans. C19 (Apr. 1970), 349-353.

Google Scholar

Cited By

View all

Maji H(2020)Computational Hardness of Collective Coin-Tossing ProtocolsEntropy10.3390/e2301004423:1(44)Online publication date: 30-Dec-2020
https://doi.org/10.3390/e23010044
Harms NChan T(2019)Testing halfspaces over rotation-invariant distributionsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310479(694-713)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310479
Neutzling AMartins MCallegaro VReis ARibas R(2017)A Simple and Effective Heuristic Method for Threshold Logic IdentificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.2729403(1-1)Online publication date: 2017
https://doi.org/10.1109/TCAD.2017.2729403
Show More Cited By

Index Terms

Chow Parameters in Threshold Logic
1. Theory of computation
  1. Logic
  2. Randomness, geometry and discrete structures

Recommendations

Threshold Gate Approximations Based on Chow Parameters

Seven methods are compared for deriving approximate realizing weights and threshold for a threshold function, given its Chow parameters. These include use of the parameters themselves, methods published by Dertouzos and the author, and several new ...
Chow parameters in pseudothreshold logic
SWAT '73: Proceedings of the 14th Annual Symposium on Switching and Automata Theory (swat 1973)

The Investigation of Chow parameters is extended to pseudothreshold functions. Pseudothreshold logic is a generalization of threshold logic. Chow parameters are a set of n + 1 integers derived from a Boolean function of n variables. The main results are:...
The impact of MOSFET's physical parameters on its threshold voltage
MINO'07: Proceedings of the 6th conference on Microelectronics, nanoelectronics, optoelectronics

The aim of this paper is to research the impact of physical parameters which characterize the MOSFET transistors structure on the threshold voltage value. It is also analysed the role of substrate (the body effect) on the threshold voltage. The MOSFET ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 18, Issue 2

April 1971

192 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321637

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1971

Published in JACM Volume 18, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
746
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)8

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Maji H(2020)Computational Hardness of Collective Coin-Tossing ProtocolsEntropy10.3390/e2301004423:1(44)Online publication date: 30-Dec-2020
https://doi.org/10.3390/e23010044
Harms NChan T(2019)Testing halfspaces over rotation-invariant distributionsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310479(694-713)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310479
Neutzling AMartins MCallegaro VReis ARibas R(2017)A Simple and Effective Heuristic Method for Threshold Logic IdentificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.2729403(1-1)Online publication date: 2017
https://doi.org/10.1109/TCAD.2017.2729403
De ADiakonikolas IFeldman VServedio R(2014)Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of HalfspacesJournal of the ACM10.1145/259077261:2(1-36)Online publication date: 24-Apr-2014
https://dl.acm.org/doi/10.1145/2590772
Palaniswamy ATragoudas S(2012)An efficient heuristic to identify threshold logic functionsACM Journal on Emerging Technologies in Computing Systems10.1145/2287696.22877028:3(1-17)Online publication date: 15-Aug-2012
https://dl.acm.org/doi/10.1145/2287696.2287702
De ADiakonikolas IFeldman VServedio RKarloff HPitassi T(2012)Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspacesProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214043(729-746)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214043
O'Donnell RServedio R(2011)The Chow Parameters ProblemSIAM Journal on Computing10.1137/09075646640:1(165-199)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1137/090756466
O'Donnell RServedio RLadner RDwork C(2008)The chow parameters problemProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374450(517-526)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374450
Servedio R(2007)Every Linear Threshold Function has a Low-Weight ApproximatorComputational Complexity10.1007/s00037-007-0228-716:2(180-209)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1007/s00037-007-0228-7
Goldberg P(2006)A Bound on the Precision Required to Estimate a Boolean Perceptron from Its Average Satisfying AssignmentSIAM Journal on Discrete Mathematics10.1137/S089548010342676520:2(328-343)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1137/S0895480103426765
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Threshold Gate Approximations Based on Chow Parameters

Chow parameters in pseudothreshold logic

The impact of MOSFET's physical parameters on its threshold voltage

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations