A Probabilistic Learning Approach for Counterexample Guided Abstraction Refinement View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Fei He , Xiaoyu Song , Ming Gu , Jiaguang Sun

ABSTRACT

The paper presents a novel probabilistic learning approach to state separation problem which occurs in the counterexample guided abstraction refinement. The method is based on the sample learning technique, evolutionary algorithm and effective probabilistic heuristics. Compared with the previous work by the sampling decision tree learning solver, the proposed method outperforms 2 to 4 orders of magnitude faster and the size of the separation set is 76% smaller on average. More... »

PAGES

39-50

References to SciGraph publications

  • 2003-02-28. Multiple-Counterexample Guided Iterative Abstraction Refinement: An Industrial Evaluation in TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS
  • 2005. Abstraction Refinement for Bounded Model Checking in COMPUTER AIDED VERIFICATION
  • 2003-02-28. Automatic Abstraction without Counterexamples in TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS
  • 2002. SAT Based Abstraction-Refinement Using ILP and Machine Learning Techniques in COMPUTER AIDED VERIFICATION
  • 2000. Counterexample-Guided Abstraction Refinement in COMPUTER AIDED VERIFICATION
  • 2002-10. An indirect genetic algorithm for set covering problems in JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Book

    TITLE

    Automated Technology for Verification and Analysis

    ISBN

    978-3-540-47237-7
    978-3-540-47238-4

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11901914_6

    DOI

    http://dx.doi.org/10.1007/11901914_6

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": "Tsinghua University", 
              "id": "https://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "Dept. Computer Science & Technology, Tsinghua University, Beijing, China", 
                "School of Software, Tsinghua University, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "He", 
            "givenName": "Fei", 
            "id": "sg:person.012660400766.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012660400766.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Portland State University", 
              "id": "https://www.grid.ac/institutes/grid.262075.4", 
              "name": [
                "Dept. ECE, Portland State University, Oregon, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Song", 
            "givenName": "Xiaoyu", 
            "id": "sg:person.016014060175.88", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016014060175.88"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tsinghua University", 
              "id": "https://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "School of Software, Tsinghua University, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gu", 
            "givenName": "Ming", 
            "id": "sg:person.015646302766.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015646302766.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tsinghua University", 
              "id": "https://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "School of Software, Tsinghua University, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sun", 
            "givenName": "Jiaguang", 
            "id": "sg:person.011411464635.59", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011411464635.59"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/162754.162852", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006593750"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45657-0_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007194068", 
              "https://doi.org/10.1007/3-540-45657-0_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36577-x_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010704177", 
              "https://doi.org/10.1007/3-540-36577-x_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36577-x_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010704177", 
              "https://doi.org/10.1007/3-540-36577-x_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36577-x_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021111277", 
              "https://doi.org/10.1007/3-540-36577-x_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36577-x_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021111277", 
              "https://doi.org/10.1007/3-540-36577-x_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10722167_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021635428", 
              "https://doi.org/10.1007/10722167_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10722167_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021635428", 
              "https://doi.org/10.1007/10722167_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1057/palgrave.jors.2601317", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030299836", 
              "https://doi.org/10.1057/palgrave.jors.2601317"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/996566.996713", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030955334"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(95)00159-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045071476"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11513988_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053666174", 
              "https://doi.org/10.1007/11513988_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11513988_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053666174", 
              "https://doi.org/10.1007/11513988_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tcad.2004.829807", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061537055"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.21236/ada293985", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091742943"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/iccad.2000.896460", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094191419"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/iccad.2003.1257811", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095061308"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/503272.503279", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098927262"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1201/9781482273960", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1108495881"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006", 
        "datePublishedReg": "2006-01-01", 
        "description": "The paper presents a novel probabilistic learning approach to state separation problem which occurs in the counterexample guided abstraction refinement. The method is based on the sample learning technique, evolutionary algorithm and effective probabilistic heuristics. Compared with the previous work by the sampling decision tree learning solver, the proposed method outperforms 2 to 4 orders of magnitude faster and the size of the separation set is 76% smaller on average.", 
        "editor": [
          {
            "familyName": "Graf", 
            "givenName": "Susanne", 
            "type": "Person"
          }, 
          {
            "familyName": "Zhang", 
            "givenName": "Wenhui", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11901914_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-47237-7", 
            "978-3-540-47238-4"
          ], 
          "name": "Automated Technology for Verification and Analysis", 
          "type": "Book"
        }, 
        "name": "A Probabilistic Learning Approach for Counterexample Guided Abstraction Refinement", 
        "pagination": "39-50", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1051993117"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11901914_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f7a9d37d51cb20a10d3926fdb4d26e2a1e40a33b94bf464b852275fe12608cde"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11901914_6", 
          "https://app.dimensions.ai/details/publication/pub.1051993117"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:37", 
        "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/0000000357_0000000357/records_99319_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11901914_6"
      }
    ]
     

    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/11901914_6'

    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/11901914_6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11901914_6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11901914_6'


     

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

    146 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11901914_6 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nadc38f52f9e7475684ef796b8633294c
    4 schema:citation sg:pub.10.1007/10722167_15
    5 sg:pub.10.1007/11513988_11
    6 sg:pub.10.1007/3-540-36577-x_13
    7 sg:pub.10.1007/3-540-36577-x_2
    8 sg:pub.10.1007/3-540-45657-0_20
    9 sg:pub.10.1057/palgrave.jors.2601317
    10 https://doi.org/10.1016/0377-2217(95)00159-x
    11 https://doi.org/10.1109/iccad.2000.896460
    12 https://doi.org/10.1109/iccad.2003.1257811
    13 https://doi.org/10.1109/tcad.2004.829807
    14 https://doi.org/10.1145/162754.162852
    15 https://doi.org/10.1145/503272.503279
    16 https://doi.org/10.1145/996566.996713
    17 https://doi.org/10.1201/9781482273960
    18 https://doi.org/10.21236/ada293985
    19 schema:datePublished 2006
    20 schema:datePublishedReg 2006-01-01
    21 schema:description The paper presents a novel probabilistic learning approach to state separation problem which occurs in the counterexample guided abstraction refinement. The method is based on the sample learning technique, evolutionary algorithm and effective probabilistic heuristics. Compared with the previous work by the sampling decision tree learning solver, the proposed method outperforms 2 to 4 orders of magnitude faster and the size of the separation set is 76% smaller on average.
    22 schema:editor Nb0279da3c81e4e039f89f137de31c06a
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N455f0a40b3fb42138c95495599244b5a
    27 schema:name A Probabilistic Learning Approach for Counterexample Guided Abstraction Refinement
    28 schema:pagination 39-50
    29 schema:productId N1cc157c952314147b1f966756f58f40b
    30 N5d2e1562a22b496e910231cb2a05e89b
    31 N708abfbf4a9746618d724694eb9450f5
    32 schema:publisher Ncab6190716694862acb70c881f966d99
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051993117
    34 https://doi.org/10.1007/11901914_6
    35 schema:sdDatePublished 2019-04-16T07:37
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher N7b2622b2217049fa9e8d203d6c0d55b1
    38 schema:url https://link.springer.com/10.1007%2F11901914_6
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset chapters
    41 rdf:type schema:Chapter
    42 N1cc157c952314147b1f966756f58f40b schema:name readcube_id
    43 schema:value f7a9d37d51cb20a10d3926fdb4d26e2a1e40a33b94bf464b852275fe12608cde
    44 rdf:type schema:PropertyValue
    45 N1cd02c02e5e24c2b8ec62bd8cdabfe65 rdf:first N783aead3c72a43389225d27d38893009
    46 rdf:rest rdf:nil
    47 N455f0a40b3fb42138c95495599244b5a schema:isbn 978-3-540-47237-7
    48 978-3-540-47238-4
    49 schema:name Automated Technology for Verification and Analysis
    50 rdf:type schema:Book
    51 N54101826f7bf46fda113053bfd7fdb92 rdf:first sg:person.016014060175.88
    52 rdf:rest N9c4354ece1944a609a06b5bb7383abe8
    53 N56b410fa23bf4022a036f0ed39894c23 schema:familyName Graf
    54 schema:givenName Susanne
    55 rdf:type schema:Person
    56 N5d2e1562a22b496e910231cb2a05e89b schema:name dimensions_id
    57 schema:value pub.1051993117
    58 rdf:type schema:PropertyValue
    59 N708abfbf4a9746618d724694eb9450f5 schema:name doi
    60 schema:value 10.1007/11901914_6
    61 rdf:type schema:PropertyValue
    62 N783aead3c72a43389225d27d38893009 schema:familyName Zhang
    63 schema:givenName Wenhui
    64 rdf:type schema:Person
    65 N7b2622b2217049fa9e8d203d6c0d55b1 schema:name Springer Nature - SN SciGraph project
    66 rdf:type schema:Organization
    67 N9c4354ece1944a609a06b5bb7383abe8 rdf:first sg:person.015646302766.82
    68 rdf:rest Nbcb38dd47ff440618ec7cf81d10d21f0
    69 Nadc38f52f9e7475684ef796b8633294c rdf:first sg:person.012660400766.65
    70 rdf:rest N54101826f7bf46fda113053bfd7fdb92
    71 Nb0279da3c81e4e039f89f137de31c06a rdf:first N56b410fa23bf4022a036f0ed39894c23
    72 rdf:rest N1cd02c02e5e24c2b8ec62bd8cdabfe65
    73 Nbcb38dd47ff440618ec7cf81d10d21f0 rdf:first sg:person.011411464635.59
    74 rdf:rest rdf:nil
    75 Ncab6190716694862acb70c881f966d99 schema:location Berlin, Heidelberg
    76 schema:name Springer Berlin Heidelberg
    77 rdf:type schema:Organisation
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Artificial Intelligence and Image Processing
    83 rdf:type schema:DefinedTerm
    84 sg:person.011411464635.59 schema:affiliation https://www.grid.ac/institutes/grid.12527.33
    85 schema:familyName Sun
    86 schema:givenName Jiaguang
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011411464635.59
    88 rdf:type schema:Person
    89 sg:person.012660400766.65 schema:affiliation https://www.grid.ac/institutes/grid.12527.33
    90 schema:familyName He
    91 schema:givenName Fei
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012660400766.65
    93 rdf:type schema:Person
    94 sg:person.015646302766.82 schema:affiliation https://www.grid.ac/institutes/grid.12527.33
    95 schema:familyName Gu
    96 schema:givenName Ming
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015646302766.82
    98 rdf:type schema:Person
    99 sg:person.016014060175.88 schema:affiliation https://www.grid.ac/institutes/grid.262075.4
    100 schema:familyName Song
    101 schema:givenName Xiaoyu
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016014060175.88
    103 rdf:type schema:Person
    104 sg:pub.10.1007/10722167_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021635428
    105 https://doi.org/10.1007/10722167_15
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/11513988_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053666174
    108 https://doi.org/10.1007/11513988_11
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/3-540-36577-x_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010704177
    111 https://doi.org/10.1007/3-540-36577-x_13
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/3-540-36577-x_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021111277
    114 https://doi.org/10.1007/3-540-36577-x_2
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/3-540-45657-0_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007194068
    117 https://doi.org/10.1007/3-540-45657-0_20
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1057/palgrave.jors.2601317 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030299836
    120 https://doi.org/10.1057/palgrave.jors.2601317
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1016/0377-2217(95)00159-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1045071476
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1109/iccad.2000.896460 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094191419
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1109/iccad.2003.1257811 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095061308
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1109/tcad.2004.829807 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061537055
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1145/162754.162852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006593750
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1145/503272.503279 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098927262
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1145/996566.996713 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030955334
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1201/9781482273960 schema:sameAs https://app.dimensions.ai/details/publication/pub.1108495881
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.21236/ada293985 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091742943
    139 rdf:type schema:CreativeWork
    140 https://www.grid.ac/institutes/grid.12527.33 schema:alternateName Tsinghua University
    141 schema:name Dept. Computer Science & Technology, Tsinghua University, Beijing, China
    142 School of Software, Tsinghua University, Beijing, China
    143 rdf:type schema:Organization
    144 https://www.grid.ac/institutes/grid.262075.4 schema:alternateName Portland State University
    145 schema:name Dept. ECE, Portland State University, Oregon, USA
    146 rdf:type schema:Organization
     




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


    ...