On the size complexity of monotone formulas

Marc Snir

doi:10.1007/3-540-10003-2_103

On the size complexity of monotone formulas

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

"Monotone" formulas, i.e. formulas using positive constants, additions and multiplications are investigated. Lower bounds on the size of monotone formulas representing specific polynomials (permanent, matrix multiplication, symmetric functions) are achieved, using a general, dynamic programming approach. These bounds are tight for the cases investigated. Some generalizations are suggested.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 7th Colloquium
Editors	Jaco de Bakker, Jan van Leeuwen
Publisher	Springer
Pages	621-631
Number of pages	11
ISBN (Print)	9783540100034
DOIs	https://doi.org/10.1007/3-540-10003-2_103
State	Published - 1980
Externally published	Yes
Event	7th International Colloquium on Automata, Languages and Programming, ICALP 1980 - Noordwijkerhout, Netherlands Duration: Jul 14 1980 → Jul 18 1980

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	85 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th International Colloquium on Automata, Languages and Programming, ICALP 1980
Country/Territory	Netherlands
City	Noordwijkerhout
Period	7/14/80 → 7/18/80

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/3-540-10003-2_103

Library availability

Discover UIUC Full Text

Cite this

Snir, M. (1980). On the size complexity of monotone formulas. In J. de Bakker, & J. van Leeuwen (Eds.), Automata, Languages and Programming - 7th Colloquium (pp. 621-631). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 85 LNCS). Springer. https://doi.org/10.1007/3-540-10003-2_103

On the size complexity of monotone formulas. / Snir, Marc.
Automata, Languages and Programming - 7th Colloquium. ed. / Jaco de Bakker; Jan van Leeuwen. Springer, 1980. p. 621-631 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 85 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Snir, M 1980, On the size complexity of monotone formulas. in J de Bakker & J van Leeuwen (eds), Automata, Languages and Programming - 7th Colloquium. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 85 LNCS, Springer, pp. 621-631, 7th International Colloquium on Automata, Languages and Programming, ICALP 1980, Noordwijkerhout, Netherlands, 7/14/80. https://doi.org/10.1007/3-540-10003-2_103

@inproceedings{38c5892dd01d4b949a601f351a416146,

title = "On the size complexity of monotone formulas",

abstract = "{"}Monotone{"} formulas, i.e. formulas using positive constants, additions and multiplications are investigated. Lower bounds on the size of monotone formulas representing specific polynomials (permanent, matrix multiplication, symmetric functions) are achieved, using a general, dynamic programming approach. These bounds are tight for the cases investigated. Some generalizations are suggested.",

author = "Marc Snir",

note = "Publisher Copyright: {\textcopyright} 1980, Springer-Verlag.; 7th International Colloquium on Automata, Languages and Programming, ICALP 1980 ; Conference date: 14-07-1980 Through 18-07-1980",

year = "1980",

doi = "10.1007/3-540-10003-2_103",

language = "English (US)",

isbn = "9783540100034",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "621--631",

editor = "{de Bakker}, Jaco and {van Leeuwen}, Jan",

booktitle = "Automata, Languages and Programming - 7th Colloquium",

address = "Germany",

}

TY - GEN

T1 - On the size complexity of monotone formulas

AU - Snir, Marc

PY - 1980

Y1 - 1980

N2 - "Monotone" formulas, i.e. formulas using positive constants, additions and multiplications are investigated. Lower bounds on the size of monotone formulas representing specific polynomials (permanent, matrix multiplication, symmetric functions) are achieved, using a general, dynamic programming approach. These bounds are tight for the cases investigated. Some generalizations are suggested.

AB - "Monotone" formulas, i.e. formulas using positive constants, additions and multiplications are investigated. Lower bounds on the size of monotone formulas representing specific polynomials (permanent, matrix multiplication, symmetric functions) are achieved, using a general, dynamic programming approach. These bounds are tight for the cases investigated. Some generalizations are suggested.

UR - http://www.scopus.com/inward/record.url?scp=57949117244&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57949117244&partnerID=8YFLogxK

U2 - 10.1007/3-540-10003-2_103

DO - 10.1007/3-540-10003-2_103

M3 - Conference contribution

AN - SCOPUS:57949117244

SN - 9783540100034

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 621

EP - 631

BT - Automata, Languages and Programming - 7th Colloquium

A2 - de Bakker, Jaco

A2 - van Leeuwen, Jan

PB - Springer

T2 - 7th International Colloquium on Automata, Languages and Programming, ICALP 1980

Y2 - 14 July 1980 through 18 July 1980

ER -

On the size complexity of monotone formulas

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this