An Effective Implementation of a Special Quantifier Elimination for a Sign Definite Condition by Logical Formula Simplification View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Hidenao Iwane , Hiroyuki Higuchi , Hirokazu Anai

ABSTRACT

This paper presents an efficient quantifier elimination algorithm tailored for a sign definite condition (SDC). The SDC for a polynomial f ∈ ℝ[x] with parametric coefficients is written as ∀ x ( x ≥ 0 → f(x) > 0). To improve the algorithm, simplification of an output formula is needed. We show a necessary condition for the SDC and an approach to simplify formulae by using a logic minimization method. Experimental results show that our approach significantly simplify formulae. More... »

PAGES

194-208

References to SciGraph publications

  • 1998. A Combinatorial Algorithm Solving Some Quantifier Elimination Problems in QUANTIFIER ELIMINATION AND CYLINDRICAL ALGEBRAIC DECOMPOSITION
  • 2011-09. A Symbolic-Numeric Approach to Multi-Objective Optimization in Manufacturing Design in MATHEMATICS IN COMPUTER SCIENCE
  • 1984. Logic Minimization Algorithms for VLSI Synthesis in NONE
  • 1998. Sturm—Habicht Sequences, Determinants and Real Roots of Univariate Polynomials in QUANTIFIER ELIMINATION AND CYLINDRICAL ALGEBRAIC DECOMPOSITION
  • 2006. New Domains for Applied Quantifier Elimination in COMPUTER ALGEBRA IN SCIENTIFIC COMPUTING
  • 2007-12. Solving and visualizing nonlinear parametric constraints in control based on quantifier elimination in APPLICABLE ALGEBRA IN ENGINEERING, COMMUNICATION AND COMPUTING
  • Book

    TITLE

    Computer Algebra in Scientific Computing

    ISBN

    978-3-319-02296-3
    978-3-319-02297-0

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-02297-0_17

    DOI

    http://dx.doi.org/10.1007/978-3-319-02297-0_17

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "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": {
              "alternateName": "Fujitsu (Japan)", 
              "id": "https://www.grid.ac/institutes/grid.418251.b", 
              "name": [
                "IT Systems Laboratories, Fujitsu Laboratories Ltd., Kamikodanaka 4-1-1, Nakahara-ku, Kawasaki\u00a0211-8588, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Iwane", 
            "givenName": "Hidenao", 
            "id": "sg:person.010140563203.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010140563203.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Fujitsu (Japan)", 
              "id": "https://www.grid.ac/institutes/grid.418251.b", 
              "name": [
                "IT Systems Laboratories, Fujitsu Laboratories Ltd., Kamikodanaka 4-1-1, Nakahara-ku, Kawasaki\u00a0211-8588, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Higuchi", 
            "givenName": "Hiroyuki", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Fujitsu (Japan)", 
              "id": "https://www.grid.ac/institutes/grid.418251.b", 
              "name": [
                "IT Systems Laboratories, Fujitsu Laboratories Ltd., Kamikodanaka 4-1-1, Nakahara-ku, Kawasaki\u00a0211-8588, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Anai", 
            "givenName": "Hirokazu", 
            "id": "sg:person.014434143753.20", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014434143753.20"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-7091-9459-1_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001753950", 
              "https://doi.org/10.1007/978-3-7091-9459-1_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00200-007-0056-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004511723", 
              "https://doi.org/10.1007/s00200-007-0056-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00200-007-0056-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004511723", 
              "https://doi.org/10.1007/s00200-007-0056-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11786-011-0097-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011222711", 
              "https://doi.org/10.1007/s11786-011-0097-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1022230131", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-2821-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022230131", 
              "https://doi.org/10.1007/978-1-4613-2821-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-2821-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022230131", 
              "https://doi.org/10.1007/978-1-4613-2821-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1993886.1993935", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022753409"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00207170600726550", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025695189"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/157485.165069", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027745982"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2752/155280107780154114", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032607609"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/968708.968710", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032819667"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11870814_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036758884", 
              "https://doi.org/10.1007/11870814_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11870814_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036758884", 
              "https://doi.org/10.1007/11870814_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-7091-9459-1_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044712691", 
              "https://doi.org/10.1007/978-3-7091-9459-1_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/157485.165071", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050129367"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2012.10.020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052827531"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013", 
        "datePublishedReg": "2013-01-01", 
        "description": "This paper presents an efficient quantifier elimination algorithm tailored for a sign definite condition (SDC). The SDC for a polynomial f\u2009\u2208\u2009\u211d[x] with parametric coefficients is written as \u2200\u2009x ( x\u2009\u2265\u20090\u2009\u2192\u2009f(x)\u2009>\u20090). To improve the algorithm, simplification of an output formula is needed. We show a necessary condition for the SDC and an approach to simplify formulae by using a logic minimization method. Experimental results show that our approach significantly simplify formulae.", 
        "editor": [
          {
            "familyName": "Gerdt", 
            "givenName": "Vladimir P.", 
            "type": "Person"
          }, 
          {
            "familyName": "Koepf", 
            "givenName": "Wolfram", 
            "type": "Person"
          }, 
          {
            "familyName": "Mayr", 
            "givenName": "Ernst W.", 
            "type": "Person"
          }, 
          {
            "familyName": "Vorozhtsov", 
            "givenName": "Evgenii V.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-02297-0_17", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-02296-3", 
            "978-3-319-02297-0"
          ], 
          "name": "Computer Algebra in Scientific Computing", 
          "type": "Book"
        }, 
        "name": "An Effective Implementation of a Special Quantifier Elimination for a Sign Definite Condition by Logical Formula Simplification", 
        "pagination": "194-208", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-02297-0_17"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e21c6c08aa41adbf47a1342e32e68e33ca8d61eb2578b17a6905c0271efa4642"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1047465633"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-02297-0_17", 
          "https://app.dimensions.ai/details/publication/pub.1047465633"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T15:23", 
        "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_8672_00000272.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-02297-0_17"
      }
    ]
     

    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/978-3-319-02297-0_17'

    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/978-3-319-02297-0_17'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-02297-0_17'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-02297-0_17'


     

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

    140 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-02297-0_17 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author Naa681825da984baebf8a656dfa275153
    4 schema:citation sg:pub.10.1007/11870814_25
    5 sg:pub.10.1007/978-1-4613-2821-6
    6 sg:pub.10.1007/978-3-7091-9459-1_14
    7 sg:pub.10.1007/978-3-7091-9459-1_19
    8 sg:pub.10.1007/s00200-007-0056-7
    9 sg:pub.10.1007/s11786-011-0097-y
    10 https://app.dimensions.ai/details/publication/pub.1022230131
    11 https://doi.org/10.1016/j.tcs.2012.10.020
    12 https://doi.org/10.1080/00207170600726550
    13 https://doi.org/10.1145/157485.165069
    14 https://doi.org/10.1145/157485.165071
    15 https://doi.org/10.1145/1993886.1993935
    16 https://doi.org/10.1145/968708.968710
    17 https://doi.org/10.2752/155280107780154114
    18 schema:datePublished 2013
    19 schema:datePublishedReg 2013-01-01
    20 schema:description This paper presents an efficient quantifier elimination algorithm tailored for a sign definite condition (SDC). The SDC for a polynomial f ∈ ℝ[x] with parametric coefficients is written as ∀ x ( x ≥ 0 → f(x) > 0). To improve the algorithm, simplification of an output formula is needed. We show a necessary condition for the SDC and an approach to simplify formulae by using a logic minimization method. Experimental results show that our approach significantly simplify formulae.
    21 schema:editor N5e41e7a4c686492aae5f7ee7dd6a5d4d
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf Nc6257912a4d2469e9aca7e7d8f67a0e1
    26 schema:name An Effective Implementation of a Special Quantifier Elimination for a Sign Definite Condition by Logical Formula Simplification
    27 schema:pagination 194-208
    28 schema:productId N2120011eccd845a794aa096df630b4fb
    29 N455f23a586104e14abda7ae6449b9cdd
    30 N521e2ba8ed174b3791420c398f01a8df
    31 schema:publisher N9c47f977e2e042d68d630d8e2db296e8
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047465633
    33 https://doi.org/10.1007/978-3-319-02297-0_17
    34 schema:sdDatePublished 2019-04-15T15:23
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher Na6f6b6d10d8742839ea265530db0d353
    37 schema:url http://link.springer.com/10.1007/978-3-319-02297-0_17
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset chapters
    40 rdf:type schema:Chapter
    41 N093f9fe387cf4ed99ffac7aa63b7b637 rdf:first Nc7beb555548048d6803bfca3874e99bb
    42 rdf:rest Nffe72970863949e9857dc4069dc2654e
    43 N1e912d382bfb4a4a99214815a3430d2e schema:familyName Gerdt
    44 schema:givenName Vladimir P.
    45 rdf:type schema:Person
    46 N2120011eccd845a794aa096df630b4fb schema:name dimensions_id
    47 schema:value pub.1047465633
    48 rdf:type schema:PropertyValue
    49 N455f23a586104e14abda7ae6449b9cdd schema:name doi
    50 schema:value 10.1007/978-3-319-02297-0_17
    51 rdf:type schema:PropertyValue
    52 N521e2ba8ed174b3791420c398f01a8df schema:name readcube_id
    53 schema:value e21c6c08aa41adbf47a1342e32e68e33ca8d61eb2578b17a6905c0271efa4642
    54 rdf:type schema:PropertyValue
    55 N5e41e7a4c686492aae5f7ee7dd6a5d4d rdf:first N1e912d382bfb4a4a99214815a3430d2e
    56 rdf:rest N63d1749cca7e41b9a7754cc036016c74
    57 N63d1749cca7e41b9a7754cc036016c74 rdf:first N897da4cb66ea44c7929f7b37db42bb54
    58 rdf:rest Nc4d8e47d1ab4459fb2436d8172f28c63
    59 N88353dda99e04b3999c6fb95deff7032 rdf:first Ne8fa7bf7585a455eb196e5b697d68a36
    60 rdf:rest rdf:nil
    61 N897da4cb66ea44c7929f7b37db42bb54 schema:familyName Koepf
    62 schema:givenName Wolfram
    63 rdf:type schema:Person
    64 N9c47f977e2e042d68d630d8e2db296e8 schema:location Cham
    65 schema:name Springer International Publishing
    66 rdf:type schema:Organisation
    67 Na6f6b6d10d8742839ea265530db0d353 schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Naa681825da984baebf8a656dfa275153 rdf:first sg:person.010140563203.82
    70 rdf:rest N093f9fe387cf4ed99ffac7aa63b7b637
    71 Nc4d8e47d1ab4459fb2436d8172f28c63 rdf:first Ne5e98fa4ec7f432682a40ba0fd4416d6
    72 rdf:rest N88353dda99e04b3999c6fb95deff7032
    73 Nc6257912a4d2469e9aca7e7d8f67a0e1 schema:isbn 978-3-319-02296-3
    74 978-3-319-02297-0
    75 schema:name Computer Algebra in Scientific Computing
    76 rdf:type schema:Book
    77 Nc7beb555548048d6803bfca3874e99bb schema:affiliation https://www.grid.ac/institutes/grid.418251.b
    78 schema:familyName Higuchi
    79 schema:givenName Hiroyuki
    80 rdf:type schema:Person
    81 Ne5e98fa4ec7f432682a40ba0fd4416d6 schema:familyName Mayr
    82 schema:givenName Ernst W.
    83 rdf:type schema:Person
    84 Ne8fa7bf7585a455eb196e5b697d68a36 schema:familyName Vorozhtsov
    85 schema:givenName Evgenii V.
    86 rdf:type schema:Person
    87 Nffe72970863949e9857dc4069dc2654e rdf:first sg:person.014434143753.20
    88 rdf:rest rdf:nil
    89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Information and Computing Sciences
    91 rdf:type schema:DefinedTerm
    92 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Information Systems
    94 rdf:type schema:DefinedTerm
    95 sg:person.010140563203.82 schema:affiliation https://www.grid.ac/institutes/grid.418251.b
    96 schema:familyName Iwane
    97 schema:givenName Hidenao
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010140563203.82
    99 rdf:type schema:Person
    100 sg:person.014434143753.20 schema:affiliation https://www.grid.ac/institutes/grid.418251.b
    101 schema:familyName Anai
    102 schema:givenName Hirokazu
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014434143753.20
    104 rdf:type schema:Person
    105 sg:pub.10.1007/11870814_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036758884
    106 https://doi.org/10.1007/11870814_25
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/978-1-4613-2821-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022230131
    109 https://doi.org/10.1007/978-1-4613-2821-6
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/978-3-7091-9459-1_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044712691
    112 https://doi.org/10.1007/978-3-7091-9459-1_14
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-7091-9459-1_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001753950
    115 https://doi.org/10.1007/978-3-7091-9459-1_19
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/s00200-007-0056-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004511723
    118 https://doi.org/10.1007/s00200-007-0056-7
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/s11786-011-0097-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1011222711
    121 https://doi.org/10.1007/s11786-011-0097-y
    122 rdf:type schema:CreativeWork
    123 https://app.dimensions.ai/details/publication/pub.1022230131 schema:CreativeWork
    124 https://doi.org/10.1016/j.tcs.2012.10.020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052827531
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1080/00207170600726550 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025695189
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1145/157485.165069 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027745982
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1145/157485.165071 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050129367
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1145/1993886.1993935 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022753409
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1145/968708.968710 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032819667
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.2752/155280107780154114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032607609
    137 rdf:type schema:CreativeWork
    138 https://www.grid.ac/institutes/grid.418251.b schema:alternateName Fujitsu (Japan)
    139 schema:name IT Systems Laboratories, Fujitsu Laboratories Ltd., Kamikodanaka 4-1-1, Nakahara-ku, Kawasaki 211-8588, Japan
    140 rdf:type schema:Organization
     




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


    ...