A Separation Bound for Real Algebraic Expressions View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2007-12-04

AUTHORS

Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt

ABSTRACT

Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real. More... »

PAGES

14-28

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-007-9132-4

DOI

http://dx.doi.org/10.1007/s00453-007-9132-4

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "ENCOM GmbH, 66740, Saarlouis, Germany", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "ENCOM GmbH, 66740, Saarlouis, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Burnikel", 
        "givenName": "Christoph", 
        "id": "sg:person.012055173114.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012055173114.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Mathematik und Informatik, Ernst-Moritz-Arndt Universit\u00e4t Greifswald, 17487, Greifswald, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5603.0", 
          "name": [
            "Institut f\u00fcr Mathematik und Informatik, Ernst-Moritz-Arndt Universit\u00e4t Greifswald, 17487, Greifswald, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Funke", 
        "givenName": "Stefan", 
        "id": "sg:person.010241426475.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010241426475.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MPI f\u00fcr Informatik, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "MPI f\u00fcr Informatik, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Fakult\u00e4t f\u00fcr Informatik, Otto-von-Guericke Universit\u00e4t Magdeburg, Universit\u00e4tsplatz 2, 39106, Magdeburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5807.a", 
          "name": [
            "Fakult\u00e4t f\u00fcr Informatik, Otto-von-Guericke Universit\u00e4t Magdeburg, Universit\u00e4tsplatz 2, 39106, Magdeburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schirra", 
        "givenName": "Stefan", 
        "id": "sg:person.016300400345.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016300400345.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MPI f\u00fcr Informatik, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "MPI f\u00fcr Informatik, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schmitt", 
        "givenName": "Susanne", 
        "id": "sg:person.014320335013.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014320335013.74"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bfb0049411", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052345663", 
          "https://doi.org/10.1007/bfb0049411"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-7091-3406-1_12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011935910", 
          "https://doi.org/10.1007/978-3-7091-3406-1_12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4613-9171-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033338345", 
          "https://doi.org/10.1007/978-1-4613-9171-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s004530010005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021040951", 
          "https://doi.org/10.1007/s004530010005"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2007-12-04", 
    "datePublishedReg": "2007-12-04", 
    "description": "Abstract\nReal algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-007-9132-4", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "55"
      }
    ], 
    "keywords": [
      "algebraic expressions", 
      "roots of polynomials", 
      "geometric algorithms", 
      "sign computation", 
      "previous bounds", 
      "separation bounds", 
      "bounds", 
      "number type", 
      "root operations", 
      "internal nodes", 
      "polynomials", 
      "computation", 
      "integers", 
      "algorithm", 
      "new separation", 
      "multiplication", 
      "sign test", 
      "subexpressions", 
      "coefficient", 
      "nodes", 
      "subtraction", 
      "implementation", 
      "operation", 
      "values", 
      "types", 
      "expression", 
      "roots", 
      "separation", 
      "addition", 
      "test", 
      "division", 
      "vitals", 
      "leaves"
    ], 
    "name": "A Separation Bound for Real Algebraic Expressions", 
    "pagination": "14-28", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012386101"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-007-9132-4"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-007-9132-4", 
      "https://app.dimensions.ai/details/publication/pub.1012386101"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_449.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-007-9132-4"
  }
]
 

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/s00453-007-9132-4'

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/s00453-007-9132-4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9132-4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9132-4'


 

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

143 TRIPLES      21 PREDICATES      61 URIs      49 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-007-9132-4 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nb4a1c330e94a43a79696ab627d7d5a6a
4 schema:citation sg:pub.10.1007/978-1-4613-9171-5
5 sg:pub.10.1007/978-3-7091-3406-1_12
6 sg:pub.10.1007/bfb0049411
7 sg:pub.10.1007/s004530010005
8 schema:datePublished 2007-12-04
9 schema:datePublishedReg 2007-12-04
10 schema:description Abstract Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real.
11 schema:genre article
12 schema:isAccessibleForFree true
13 schema:isPartOf N006fc7e656794528841a39e2921d2ef8
14 Nbafae521a95246dabb5de6d6247c8e93
15 sg:journal.1047644
16 schema:keywords addition
17 algebraic expressions
18 algorithm
19 bounds
20 coefficient
21 computation
22 division
23 expression
24 geometric algorithms
25 implementation
26 integers
27 internal nodes
28 leaves
29 multiplication
30 new separation
31 nodes
32 number type
33 operation
34 polynomials
35 previous bounds
36 root operations
37 roots
38 roots of polynomials
39 separation
40 separation bounds
41 sign computation
42 sign test
43 subexpressions
44 subtraction
45 test
46 types
47 values
48 vitals
49 schema:name A Separation Bound for Real Algebraic Expressions
50 schema:pagination 14-28
51 schema:productId N8e05e150bcf24aacaade7bad1779e983
52 Nba002b6f5b5d4cfdb0f2b3f1ceb6d8da
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012386101
54 https://doi.org/10.1007/s00453-007-9132-4
55 schema:sdDatePublished 2022-09-02T15:52
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N2d80f75116034599b32750238d27b8b2
58 schema:url https://doi.org/10.1007/s00453-007-9132-4
59 sgo:license sg:explorer/license/
60 sgo:sdDataset articles
61 rdf:type schema:ScholarlyArticle
62 N006fc7e656794528841a39e2921d2ef8 schema:volumeNumber 55
63 rdf:type schema:PublicationVolume
64 N0a4e5ea4c0274e088c99bb72eafbf634 rdf:first sg:person.011757371347.43
65 rdf:rest N1b9d12c791274e238a168a8f78b3471f
66 N1b9d12c791274e238a168a8f78b3471f rdf:first sg:person.016300400345.22
67 rdf:rest Ned0d2cfbe9ad47a8830dc28a4857abdc
68 N2d80f75116034599b32750238d27b8b2 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 N78374efafb5a4d11bc9d43a722db4334 rdf:first sg:person.010241426475.39
71 rdf:rest N0a4e5ea4c0274e088c99bb72eafbf634
72 N8e05e150bcf24aacaade7bad1779e983 schema:name dimensions_id
73 schema:value pub.1012386101
74 rdf:type schema:PropertyValue
75 Nb4a1c330e94a43a79696ab627d7d5a6a rdf:first sg:person.012055173114.53
76 rdf:rest N78374efafb5a4d11bc9d43a722db4334
77 Nba002b6f5b5d4cfdb0f2b3f1ceb6d8da schema:name doi
78 schema:value 10.1007/s00453-007-9132-4
79 rdf:type schema:PropertyValue
80 Nbafae521a95246dabb5de6d6247c8e93 schema:issueNumber 1
81 rdf:type schema:PublicationIssue
82 Ned0d2cfbe9ad47a8830dc28a4857abdc rdf:first sg:person.014320335013.74
83 rdf:rest rdf:nil
84 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
85 schema:name Mathematical Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
88 schema:name Pure Mathematics
89 rdf:type schema:DefinedTerm
90 sg:journal.1047644 schema:issn 0178-4617
91 1432-0541
92 schema:name Algorithmica
93 schema:publisher Springer Nature
94 rdf:type schema:Periodical
95 sg:person.010241426475.39 schema:affiliation grid-institutes:grid.5603.0
96 schema:familyName Funke
97 schema:givenName Stefan
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010241426475.39
99 rdf:type schema:Person
100 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
101 schema:familyName Mehlhorn
102 schema:givenName Kurt
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
104 rdf:type schema:Person
105 sg:person.012055173114.53 schema:affiliation grid-institutes:None
106 schema:familyName Burnikel
107 schema:givenName Christoph
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012055173114.53
109 rdf:type schema:Person
110 sg:person.014320335013.74 schema:affiliation grid-institutes:grid.419528.3
111 schema:familyName Schmitt
112 schema:givenName Susanne
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014320335013.74
114 rdf:type schema:Person
115 sg:person.016300400345.22 schema:affiliation grid-institutes:grid.5807.a
116 schema:familyName Schirra
117 schema:givenName Stefan
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016300400345.22
119 rdf:type schema:Person
120 sg:pub.10.1007/978-1-4613-9171-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033338345
121 https://doi.org/10.1007/978-1-4613-9171-5
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/978-3-7091-3406-1_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011935910
124 https://doi.org/10.1007/978-3-7091-3406-1_12
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/bfb0049411 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052345663
127 https://doi.org/10.1007/bfb0049411
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/s004530010005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021040951
130 https://doi.org/10.1007/s004530010005
131 rdf:type schema:CreativeWork
132 grid-institutes:None schema:alternateName ENCOM GmbH, 66740, Saarlouis, Germany
133 schema:name ENCOM GmbH, 66740, Saarlouis, Germany
134 rdf:type schema:Organization
135 grid-institutes:grid.419528.3 schema:alternateName MPI für Informatik, 66123, Saarbrücken, Germany
136 schema:name MPI für Informatik, 66123, Saarbrücken, Germany
137 rdf:type schema:Organization
138 grid-institutes:grid.5603.0 schema:alternateName Institut für Mathematik und Informatik, Ernst-Moritz-Arndt Universität Greifswald, 17487, Greifswald, Germany
139 schema:name Institut für Mathematik und Informatik, Ernst-Moritz-Arndt Universität Greifswald, 17487, Greifswald, Germany
140 rdf:type schema:Organization
141 grid-institutes:grid.5807.a schema:alternateName Fakultät für Informatik, Otto-von-Guericke Universität Magdeburg, Universitätsplatz 2, 39106, Magdeburg, Germany
142 schema:name Fakultät für Informatik, Otto-von-Guericke Universität Magdeburg, Universitätsplatz 2, 39106, Magdeburg, Germany
143 rdf:type schema:Organization
 




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


...