Gröbner bases: Strategies and applications View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1993

AUTHORS

Eric Monfroy

ABSTRACT

Many problems of computational geometry involve non linear polynomials. Many of these problems can be solved with easy algorithms after transforming the polynomial set involved in their specification into Gröbner bases form. Gröbner bases of a system of polynomials are canonical finite sets of multivariate polynomials which define the same algebraic structure as the initial polynomial system. But the computation of Gröbner bases requires a large amount of time and space. However some strategies can be introduced to improve the computation. In this paper, we shortly introduce basic notions of Gröbner bases. Then we propose an algorithm for their computation which is based on a completion procedure for rewrite systems. This algorithm is extended with an orthogonal set of selection strategies which improve each sub-algorithms (reduction, inter reduction, critical pair choice). At last we discuss the use of the strategies applied to some examples (as a restriction of the well known piano mover's problem). More... »

PAGES

133-151

Book

TITLE

Artificial Intelligence and Symbolic Mathematical Computing

ISBN

978-3-540-57322-7
978-3-540-48063-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57322-4_9

DOI

http://dx.doi.org/10.1007/3-540-57322-4_9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1018585394


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "ECRC European Computer-industry Research Centre, Arabellastr. 17, D-8000\u00a0Munich 81, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Monfroy", 
        "givenName": "Eric", 
        "type": "Person"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "Many problems of computational geometry involve non linear polynomials. Many of these problems can be solved with easy algorithms after transforming the polynomial set involved in their specification into Gr\u00f6bner bases form. Gr\u00f6bner bases of a system of polynomials are canonical finite sets of multivariate polynomials which define the same algebraic structure as the initial polynomial system. But the computation of Gr\u00f6bner bases requires a large amount of time and space. However some strategies can be introduced to improve the computation. In this paper, we shortly introduce basic notions of Gr\u00f6bner bases. Then we propose an algorithm for their computation which is based on a completion procedure for rewrite systems. This algorithm is extended with an orthogonal set of selection strategies which improve each sub-algorithms (reduction, inter reduction, critical pair choice). At last we discuss the use of the strategies applied to some examples (as a restriction of the well known piano mover's problem).", 
    "editor": [
      {
        "familyName": "Calmet", 
        "givenName": "Jacques", 
        "type": "Person"
      }, 
      {
        "familyName": "Campbell", 
        "givenName": "John A.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57322-4_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57322-7", 
        "978-3-540-48063-1"
      ], 
      "name": "Artificial Intelligence and Symbolic Mathematical Computing", 
      "type": "Book"
    }, 
    "name": "Gr\u00f6bner bases: Strategies and applications", 
    "pagination": "133-151", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57322-4_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "588d1c0ee34854f83b8bb1eb634bb8c618bdd01c8e9bd72dc18a70f450222151"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018585394"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57322-4_9", 
      "https://app.dimensions.ai/details/publication/pub.1018585394"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T22:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8695_00000032.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-57322-4_9"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-57322-4_9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-57322-4_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57322-4_9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57322-4_9'


 

This table displays all metadata directly associated to this object as RDF triples.

68 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57322-4_9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8b04effec73b460880005d4e48858de5
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 schema:description Many problems of computational geometry involve non linear polynomials. Many of these problems can be solved with easy algorithms after transforming the polynomial set involved in their specification into Gröbner bases form. Gröbner bases of a system of polynomials are canonical finite sets of multivariate polynomials which define the same algebraic structure as the initial polynomial system. But the computation of Gröbner bases requires a large amount of time and space. However some strategies can be introduced to improve the computation. In this paper, we shortly introduce basic notions of Gröbner bases. Then we propose an algorithm for their computation which is based on a completion procedure for rewrite systems. This algorithm is extended with an orthogonal set of selection strategies which improve each sub-algorithms (reduction, inter reduction, critical pair choice). At last we discuss the use of the strategies applied to some examples (as a restriction of the well known piano mover's problem).
7 schema:editor N377892ac28a6462d8c7255aef86cb2bc
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8fa3fff6039043b7a078bef3bdcb2b97
12 schema:name Gröbner bases: Strategies and applications
13 schema:pagination 133-151
14 schema:productId N276a966e81974e4ba0a9cd76c1e485a8
15 N4427307998294986a39d51ab20a4cdeb
16 N85b1364c70ed4a0c9d36c697685d3a14
17 schema:publisher Ncf5af3719ac047cb96560a18a257137c
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018585394
19 https://doi.org/10.1007/3-540-57322-4_9
20 schema:sdDatePublished 2019-04-15T22:41
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nb7e1befcc3f4405b9bf2f03b8178e23f
23 schema:url http://link.springer.com/10.1007/3-540-57322-4_9
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N276a966e81974e4ba0a9cd76c1e485a8 schema:name readcube_id
28 schema:value 588d1c0ee34854f83b8bb1eb634bb8c618bdd01c8e9bd72dc18a70f450222151
29 rdf:type schema:PropertyValue
30 N377892ac28a6462d8c7255aef86cb2bc rdf:first Naf6d8e14b6b744debdca0bbbf25954ba
31 rdf:rest N496cba097e1d430289f4188cefdbd1a6
32 N4427307998294986a39d51ab20a4cdeb schema:name dimensions_id
33 schema:value pub.1018585394
34 rdf:type schema:PropertyValue
35 N496cba097e1d430289f4188cefdbd1a6 rdf:first Ne470c9b9de46414198d6a15869c9b4b4
36 rdf:rest rdf:nil
37 N5cfc6f6c97f64f4db39e7979cdbdbd41 schema:affiliation Neab18473aae14b95a6b870700a5c3ffa
38 schema:familyName Monfroy
39 schema:givenName Eric
40 rdf:type schema:Person
41 N85b1364c70ed4a0c9d36c697685d3a14 schema:name doi
42 schema:value 10.1007/3-540-57322-4_9
43 rdf:type schema:PropertyValue
44 N8b04effec73b460880005d4e48858de5 rdf:first N5cfc6f6c97f64f4db39e7979cdbdbd41
45 rdf:rest rdf:nil
46 N8fa3fff6039043b7a078bef3bdcb2b97 schema:isbn 978-3-540-48063-1
47 978-3-540-57322-7
48 schema:name Artificial Intelligence and Symbolic Mathematical Computing
49 rdf:type schema:Book
50 Naf6d8e14b6b744debdca0bbbf25954ba schema:familyName Calmet
51 schema:givenName Jacques
52 rdf:type schema:Person
53 Nb7e1befcc3f4405b9bf2f03b8178e23f schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 Ncf5af3719ac047cb96560a18a257137c schema:location Berlin, Heidelberg
56 schema:name Springer Berlin Heidelberg
57 rdf:type schema:Organisation
58 Ne470c9b9de46414198d6a15869c9b4b4 schema:familyName Campbell
59 schema:givenName John A.
60 rdf:type schema:Person
61 Neab18473aae14b95a6b870700a5c3ffa schema:name ECRC European Computer-industry Research Centre, Arabellastr. 17, D-8000 Munich 81, Germany
62 rdf:type schema:Organization
63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
64 schema:name Information and Computing Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
67 schema:name Computation Theory and Mathematics
68 rdf:type schema:DefinedTerm
 




Preview window. Press ESC to close (or click here)


...