Negative Ternary Set-Sharing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Eric Trias , Jorge Navas , Elena S. Ackley , Stephanie Forrest , M. Hermenegildo

ABSTRACT

The Set-Sharing domain has been widely used to infer at compile-time interesting properties of logic programs such as occurs-check reduction, automatic parallelization, and finite-tree analysis. However, performing abstract unification in this domain requires a closure operation that increases the number of sharing groups exponentially. Much attention has been given to mitigating this key inefficiency in this otherwise very useful domain. In this paper we present a novel approach to Set-Sharing: we define a new representation that leverages the complement (or negative) sharing relationships of the original sharing set, without loss of accuracy. Intuitively, given an abstract state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$sh_{\mathcal{V}}$\end{document} over the finite set of variables of interest \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{V}$\end{document}, its negative representation is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\wp(\mathcal{V}) \setminus sh_{\mathcal{V}}$\end{document}. Using this encoding during analysis dramatically reduces the number of elements that need to be represented in the abstract states and during abstract unification as the cardinality of the original set grows toward \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$2^{|\mathcal{V}|}$\end{document}. To further compress the number of elements, we express the set-sharing relationships through a set of ternary strings that compacts the representation by eliminating redundancies among the sharing sets. Our experiments show that our approach can compress the number of relationships, reducing significantly the memory usage and running time of all abstract operations, including abstract unification. More... »

PAGES

301-316

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-89982-2_30

DOI

http://dx.doi.org/10.1007/978-3-540-89982-2_30

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Air Force Institute of Technology, USA", 
          "id": "http://www.grid.ac/institutes/grid.427848.5", 
          "name": [
            "University of New Mexico, USA", 
            "Air Force Institute of Technology, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Trias", 
        "givenName": "Eric", 
        "id": "sg:person.013203266625.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013203266625.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of New Mexico, USA", 
          "id": "http://www.grid.ac/institutes/grid.266832.b", 
          "name": [
            "University of New Mexico, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Navas", 
        "givenName": "Jorge", 
        "id": "sg:person.015151712621.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015151712621.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of New Mexico, USA", 
          "id": "http://www.grid.ac/institutes/grid.266832.b", 
          "name": [
            "University of New Mexico, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ackley", 
        "givenName": "Elena S.", 
        "id": "sg:person.01124410703.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01124410703.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of New Mexico, USA", 
          "id": "http://www.grid.ac/institutes/grid.266832.b", 
          "name": [
            "University of New Mexico, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Forrest", 
        "givenName": "Stephanie", 
        "id": "sg:person.0712103012.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technical U. of Madrid (Spain) and IMDEA-Software, Spain", 
          "id": "http://www.grid.ac/institutes/grid.482873.2", 
          "name": [
            "University of New Mexico, USA", 
            "Technical U. of Madrid (Spain) and IMDEA-Software, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hermenegildo", 
        "givenName": "M.", 
        "id": "sg:person.016231041373.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016231041373.11"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "The Set-Sharing domain has been widely used to infer at compile-time interesting properties of logic programs such as occurs-check reduction, automatic parallelization, and finite-tree analysis. However, performing abstract unification in this domain requires a closure operation that increases the number of sharing groups exponentially. Much attention has been given to mitigating this key inefficiency in this otherwise very useful domain. In this paper we present a novel approach to Set-Sharing: we define a new representation that leverages the complement (or negative) sharing relationships of the original sharing set, without loss of accuracy. Intuitively, given an abstract state \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$sh_{\\mathcal{V}}$\\end{document} over the finite set of variables of interest \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{V}$\\end{document}, its negative representation is \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\wp(\\mathcal{V}) \\setminus sh_{\\mathcal{V}}$\\end{document}. Using this encoding during analysis dramatically reduces the number of elements that need to be represented in the abstract states and during abstract unification as the cardinality of the original set grows toward \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$2^{|\\mathcal{V}|}$\\end{document}. To further compress the number of elements, we express the set-sharing relationships through a set of ternary strings that compacts the representation by eliminating redundancies among the sharing sets. Our experiments show that our approach can compress the number of relationships, reducing significantly the memory usage and running time of all abstract operations, including abstract unification.", 
    "editor": [
      {
        "familyName": "Garcia de la Banda", 
        "givenName": "Maria", 
        "type": "Person"
      }, 
      {
        "familyName": "Pontelli", 
        "givenName": "Enrico", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-89982-2_30", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-89981-5", 
        "978-3-540-89982-2"
      ], 
      "name": "Logic Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "abstract unification", 
      "sharing set", 
      "abstract states", 
      "automatic parallelization", 
      "memory usage", 
      "abstract operations", 
      "logic programs", 
      "number of elements", 
      "loss of accuracy", 
      "useful domain", 
      "novel approach", 
      "new representation", 
      "original set", 
      "Key inefficiencies", 
      "set", 
      "representation", 
      "number of relationships", 
      "finite set", 
      "parallelization", 
      "domain", 
      "redundancy", 
      "ternary strings", 
      "closure operation", 
      "operation", 
      "encoding", 
      "unification", 
      "usage", 
      "cardinality", 
      "interesting properties", 
      "accuracy", 
      "number", 
      "inefficiency", 
      "strings", 
      "elements", 
      "experiments", 
      "state", 
      "interest", 
      "program", 
      "time", 
      "attention", 
      "analysis", 
      "variables", 
      "relationship", 
      "negative representations", 
      "complement", 
      "properties", 
      "reduction", 
      "loss", 
      "group", 
      "ternary", 
      "approach", 
      "paper", 
      "compile-time interesting properties", 
      "occurs-check reduction", 
      "finite-tree analysis", 
      "Set-Sharing", 
      "original sharing set", 
      "set-sharing relationships", 
      "Negative Ternary"
    ], 
    "name": "Negative Ternary Set-Sharing", 
    "pagination": "301-316", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010645867"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-89982-2_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-89982-2_30", 
      "https://app.dimensions.ai/details/publication/pub.1010645867"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_27.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-89982-2_30"
  }
]
 

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-540-89982-2_30'

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-540-89982-2_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-89982-2_30'

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-540-89982-2_30'


 

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

160 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-89982-2_30 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author Nb2b7d8ee6ea448b4b51253fa609127d1
4 schema:datePublished 2008
5 schema:datePublishedReg 2008-01-01
6 schema:description The Set-Sharing domain has been widely used to infer at compile-time interesting properties of logic programs such as occurs-check reduction, automatic parallelization, and finite-tree analysis. However, performing abstract unification in this domain requires a closure operation that increases the number of sharing groups exponentially. Much attention has been given to mitigating this key inefficiency in this otherwise very useful domain. In this paper we present a novel approach to Set-Sharing: we define a new representation that leverages the complement (or negative) sharing relationships of the original sharing set, without loss of accuracy. Intuitively, given an abstract state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$sh_{\mathcal{V}}$\end{document} over the finite set of variables of interest \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{V}$\end{document}, its negative representation is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\wp(\mathcal{V}) \setminus sh_{\mathcal{V}}$\end{document}. Using this encoding during analysis dramatically reduces the number of elements that need to be represented in the abstract states and during abstract unification as the cardinality of the original set grows toward \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$2^{|\mathcal{V}|}$\end{document}. To further compress the number of elements, we express the set-sharing relationships through a set of ternary strings that compacts the representation by eliminating redundancies among the sharing sets. Our experiments show that our approach can compress the number of relationships, reducing significantly the memory usage and running time of all abstract operations, including abstract unification.
7 schema:editor Ndb5187cf7c48435ba177061bddd28a62
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfb6727771dd4481bb823580279f114ec
12 schema:keywords Key inefficiencies
13 Negative Ternary
14 Set-Sharing
15 abstract operations
16 abstract states
17 abstract unification
18 accuracy
19 analysis
20 approach
21 attention
22 automatic parallelization
23 cardinality
24 closure operation
25 compile-time interesting properties
26 complement
27 domain
28 elements
29 encoding
30 experiments
31 finite set
32 finite-tree analysis
33 group
34 inefficiency
35 interest
36 interesting properties
37 logic programs
38 loss
39 loss of accuracy
40 memory usage
41 negative representations
42 new representation
43 novel approach
44 number
45 number of elements
46 number of relationships
47 occurs-check reduction
48 operation
49 original set
50 original sharing set
51 paper
52 parallelization
53 program
54 properties
55 reduction
56 redundancy
57 relationship
58 representation
59 set
60 set-sharing relationships
61 sharing set
62 state
63 strings
64 ternary
65 ternary strings
66 time
67 unification
68 usage
69 useful domain
70 variables
71 schema:name Negative Ternary Set-Sharing
72 schema:pagination 301-316
73 schema:productId Nd0c805c48a4e4dc9af87824b1a9003f3
74 Ndf69341691da4c26a09e2c4bfc648d2a
75 schema:publisher Na29f29f2a9844dff82ac574f016405d9
76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010645867
77 https://doi.org/10.1007/978-3-540-89982-2_30
78 schema:sdDatePublished 2021-12-01T20:02
79 schema:sdLicense https://scigraph.springernature.com/explorer/license/
80 schema:sdPublisher Nd6b0b7b938c64fa4a64d84663f5f335a
81 schema:url https://doi.org/10.1007/978-3-540-89982-2_30
82 sgo:license sg:explorer/license/
83 sgo:sdDataset chapters
84 rdf:type schema:Chapter
85 N3aead24606a04790bb5f31e6bd643e24 rdf:first sg:person.01124410703.95
86 rdf:rest Nbce62cbb5adc4a9b90ff93266e24d129
87 N88a2a4a479904c0c9eb1dc05feca39e4 rdf:first sg:person.015151712621.06
88 rdf:rest N3aead24606a04790bb5f31e6bd643e24
89 N8f374b38b48646d1a57aab4391990427 rdf:first Nfaadc735e26f4a138fc5ac8204692de7
90 rdf:rest rdf:nil
91 Na29f29f2a9844dff82ac574f016405d9 schema:name Springer Nature
92 rdf:type schema:Organisation
93 Nac0f1136226b4032a45779684e80a69d schema:familyName Garcia de la Banda
94 schema:givenName Maria
95 rdf:type schema:Person
96 Nb2b7d8ee6ea448b4b51253fa609127d1 rdf:first sg:person.013203266625.18
97 rdf:rest N88a2a4a479904c0c9eb1dc05feca39e4
98 Nbce62cbb5adc4a9b90ff93266e24d129 rdf:first sg:person.0712103012.64
99 rdf:rest Nd0283086cfb248e288273808807dc3f5
100 Nd0283086cfb248e288273808807dc3f5 rdf:first sg:person.016231041373.11
101 rdf:rest rdf:nil
102 Nd0c805c48a4e4dc9af87824b1a9003f3 schema:name dimensions_id
103 schema:value pub.1010645867
104 rdf:type schema:PropertyValue
105 Nd6b0b7b938c64fa4a64d84663f5f335a schema:name Springer Nature - SN SciGraph project
106 rdf:type schema:Organization
107 Ndb5187cf7c48435ba177061bddd28a62 rdf:first Nac0f1136226b4032a45779684e80a69d
108 rdf:rest N8f374b38b48646d1a57aab4391990427
109 Ndf69341691da4c26a09e2c4bfc648d2a schema:name doi
110 schema:value 10.1007/978-3-540-89982-2_30
111 rdf:type schema:PropertyValue
112 Nfaadc735e26f4a138fc5ac8204692de7 schema:familyName Pontelli
113 schema:givenName Enrico
114 rdf:type schema:Person
115 Nfb6727771dd4481bb823580279f114ec schema:isbn 978-3-540-89981-5
116 978-3-540-89982-2
117 schema:name Logic Programming
118 rdf:type schema:Book
119 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
120 schema:name Psychology and Cognitive Sciences
121 rdf:type schema:DefinedTerm
122 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
123 schema:name Psychology
124 rdf:type schema:DefinedTerm
125 sg:person.01124410703.95 schema:affiliation grid-institutes:grid.266832.b
126 schema:familyName Ackley
127 schema:givenName Elena S.
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01124410703.95
129 rdf:type schema:Person
130 sg:person.013203266625.18 schema:affiliation grid-institutes:grid.427848.5
131 schema:familyName Trias
132 schema:givenName Eric
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013203266625.18
134 rdf:type schema:Person
135 sg:person.015151712621.06 schema:affiliation grid-institutes:grid.266832.b
136 schema:familyName Navas
137 schema:givenName Jorge
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015151712621.06
139 rdf:type schema:Person
140 sg:person.016231041373.11 schema:affiliation grid-institutes:grid.482873.2
141 schema:familyName Hermenegildo
142 schema:givenName M.
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016231041373.11
144 rdf:type schema:Person
145 sg:person.0712103012.64 schema:affiliation grid-institutes:grid.266832.b
146 schema:familyName Forrest
147 schema:givenName Stephanie
148 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64
149 rdf:type schema:Person
150 grid-institutes:grid.266832.b schema:alternateName University of New Mexico, USA
151 schema:name University of New Mexico, USA
152 rdf:type schema:Organization
153 grid-institutes:grid.427848.5 schema:alternateName Air Force Institute of Technology, USA
154 schema:name Air Force Institute of Technology, USA
155 University of New Mexico, USA
156 rdf:type schema:Organization
157 grid-institutes:grid.482873.2 schema:alternateName Technical U. of Madrid (Spain) and IMDEA-Software, Spain
158 schema:name Technical U. of Madrid (Spain) and IMDEA-Software, Spain
159 University of New Mexico, USA
160 rdf:type schema:Organization
 




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


...