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

Pages | 621-631 |

Number of pages | 11 |

ISBN (Print) | 9783540100034 |

DOIs | |

State | Published - Jan 1 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 | Netherlands |

City | Noordwijkerhout |

Period | 7/14/80 → 7/18/80 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*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.

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

*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

}

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 -