Optimal gröbner base algorithms for binomial ideals

Ulla Koppenhagen, Ernst W. Mayr

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

2 Zitate (Scopus)

Abstract

Little is known about upper complexity bounds for the normal form algorithms which transform a given polynomial ideal basis into a Gröbner basis. In this paper, we exhibit an optimal, exponential space algorithm for generating the reduced Gröbner basis of binomial ideals. This result is then applied to derive space optimal decision procedures for the finite enumeration and subword problems for commutative semigroups.

OriginalspracheEnglisch
TitelAutomata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
Redakteure/-innenFriedhelm Meyer auf der Heide, Burkhard Monien
Herausgeber (Verlag)Springer Verlag
Seiten244-255
Seitenumfang12
ISBN (Print)3540614400, 9783540614401
DOIs
PublikationsstatusVeröffentlicht - 1996
Veranstaltung23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996 - Paderborn, Deutschland
Dauer: 8 Juli 199612 Juli 1996

Publikationsreihe

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

Konferenz

Konferenz23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996
Land/GebietDeutschland
OrtPaderborn
Zeitraum8/07/9612/07/96

Fingerprint

Untersuchen Sie die Forschungsthemen von „Optimal gröbner base algorithms for binomial ideals“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren