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/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/s004530010005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021040951", 
          "https://doi.org/10.1007/s004530010005"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "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-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"
      }
    ], 
    "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-11-24T20:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_434.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 N8581f7e62a564f5bbd56f9b0a10eb1b2
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 N2557b42c6d93477ba52b334979dc6040
14 Nf9c77bde9e964901863b1f288d129dc1
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 N46b0aa1483194c32b690896ec9745c53
52 Nca8622b82c994b05ae01a67d8cc4d296
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-11-24T20:52
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N86a9645f37c5479c8c9d66d636c35d4b
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 N0d6de7e861054d938c158a8e9c4b2285 rdf:first sg:person.014320335013.74
63 rdf:rest rdf:nil
64 N2557b42c6d93477ba52b334979dc6040 schema:issueNumber 1
65 rdf:type schema:PublicationIssue
66 N46b0aa1483194c32b690896ec9745c53 schema:name doi
67 schema:value 10.1007/s00453-007-9132-4
68 rdf:type schema:PropertyValue
69 N8581f7e62a564f5bbd56f9b0a10eb1b2 rdf:first sg:person.012055173114.53
70 rdf:rest N90f0c7f469c74476b2d2994e8f2e90f8
71 N86a9645f37c5479c8c9d66d636c35d4b schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N90f0c7f469c74476b2d2994e8f2e90f8 rdf:first sg:person.010241426475.39
74 rdf:rest Nf9d729979e204a82bd032b99d6b18749
75 Nca8622b82c994b05ae01a67d8cc4d296 schema:name dimensions_id
76 schema:value pub.1012386101
77 rdf:type schema:PropertyValue
78 Ne65e0a74edff4d43a55a5fa43fe68735 rdf:first sg:person.016300400345.22
79 rdf:rest N0d6de7e861054d938c158a8e9c4b2285
80 Nf9c77bde9e964901863b1f288d129dc1 schema:volumeNumber 55
81 rdf:type schema:PublicationVolume
82 Nf9d729979e204a82bd032b99d6b18749 rdf:first sg:person.011757371347.43
83 rdf:rest Ne65e0a74edff4d43a55a5fa43fe68735
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)


...