On the size complexity of monotone formulas

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 7th Colloquium
EditorsJaco de Bakker, Jan van Leeuwen
PublisherSpringer-Verlag
Pages621-631
Number of pages11
ISBN (Print)9783540100034
DOIs
StatePublished - Jan 1 1980
Externally publishedYes
Event7th International Colloquium on Automata, Languages and Programming, ICALP 1980 - Noordwijkerhout, Netherlands
Duration: Jul 14 1980Jul 18 1980

Publication series

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

Other

Other7th International Colloquium on Automata, Languages and Programming, ICALP 1980
CountryNetherlands
CityNoordwijkerhout
Period7/14/807/18/80

Fingerprint

Dynamic programming
Monotone
Polynomials
Matrix multiplication
Symmetric Functions
Dynamic Programming
Multiplication
Lower bound
Polynomial

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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-Verlag. 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-Verlag, 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 proceedingConference 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-Verlag, 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
Snir M. On the size complexity of monotone formulas. In de Bakker J, van Leeuwen J, editors, Automata, Languages and Programming - 7th Colloquium. Springer-Verlag. 1980. p. 621-631. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-10003-2_103
Snir, Marc. / On the size complexity of monotone formulas. Automata, Languages and Programming - 7th Colloquium. editor / Jaco de Bakker ; Jan van Leeuwen. Springer-Verlag, 1980. pp. 621-631 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@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",
year = "1980",
month = "1",
day = "1",
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-Verlag",
pages = "621--631",
editor = "{de Bakker}, Jaco and {van Leeuwen}, Jan",
booktitle = "Automata, Languages and Programming - 7th Colloquium",

}

TY - GEN

T1 - On the size complexity of monotone formulas

AU - Snir, Marc

PY - 1980/1/1

Y1 - 1980/1/1

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-Verlag

ER -