Decidability for Entailments of Symbolic Heaps with Arrays Article Swipe
Daisuke Kimura
,
Makoto Tatsuta
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.23638/lmcs-17(2:15)2021
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.23638/lmcs-17(2:15)2021
This paper presents two decidability results on the validity checking problem for entailments of symbolic heaps in separation logic with Presburger arithmetic and arrays. The first result is for a system with arrays and existential quantifiers. The correctness of the decision procedure is proved under the condition that sizes of arrays in the succedent are not existentially quantified. This condition is different from that proposed by Brotherston et al. in 2017 and one of them does not imply the other. The main idea is a novel translation from an entailment of symbolic heaps into a formula in Presburger arithmetic. The second result is the decidability for a system with both arrays and lists. The key idea is to extend the unroll collapse technique proposed by Berdine et al. in 2005 to arrays and arithmetic as well as double-linked lists.
Related Topics
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doaj.org/article/fbb8e86a1b054447b57cc4d8f84f3fe0
- OA Status
- green
- Cited By
- 2
- References
- 20
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3165223290
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3165223290Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.23638/lmcs-17(2:15)2021Digital Object Identifier
- Title
-
Decidability for Entailments of Symbolic Heaps with ArraysWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-05-01Full publication date if available
- Authors
-
Daisuke Kimura, Makoto TatsutaList of authors in order
- Landing page
-
https://doaj.org/article/fbb8e86a1b054447b57cc4d8f84f3fe0Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://doaj.org/article/fbb8e86a1b054447b57cc4d8f84f3fe0Direct OA link when available
- Concepts
-
Decidability, Computer science, Programming language, Business, Theoretical computer scienceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
2Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 2Per-year citation counts (last 5 years)
- References (count)
-
20Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3165223290 |
|---|---|
| doi | https://doi.org/10.23638/lmcs-17(2:15)2021 |
| ids.mag | 3165223290 |
| ids.openalex | https://openalex.org/W3165223290 |
| fwci | 0.0 |
| type | article |
| title | Decidability for Entailments of Symbolic Heaps with Arrays |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10126 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998000264167786 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Logic, programming, and type systems |
| topics[1].id | https://openalex.org/T10142 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9993000030517578 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Formal Methods in Verification |
| topics[2].id | https://openalex.org/T11567 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9991999864578247 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | semigroups and automata theory |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C153269930 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6625587344169617 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q430001 |
| concepts[0].display_name | Decidability |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.598602294921875 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C199360897 |
| concepts[2].level | 1 |
| concepts[2].score | 0.4854474663734436 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[2].display_name | Programming language |
| concepts[3].id | https://openalex.org/C144133560 |
| concepts[3].level | 0 |
| concepts[3].score | 0.3781946301460266 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q4830453 |
| concepts[3].display_name | Business |
| concepts[4].id | https://openalex.org/C80444323 |
| concepts[4].level | 1 |
| concepts[4].score | 0.28301772475242615 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[4].display_name | Theoretical computer science |
| keywords[0].id | https://openalex.org/keywords/decidability |
| keywords[0].score | 0.6625587344169617 |
| keywords[0].display_name | Decidability |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.598602294921875 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/programming-language |
| keywords[2].score | 0.4854474663734436 |
| keywords[2].display_name | Programming language |
| keywords[3].id | https://openalex.org/keywords/business |
| keywords[3].score | 0.3781946301460266 |
| keywords[3].display_name | Business |
| keywords[4].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[4].score | 0.28301772475242615 |
| keywords[4].display_name | Theoretical computer science |
| language | en |
| locations[0].id | pmh:oai:doaj.org/article:fbb8e86a1b054447b57cc4d8f84f3fe0 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306401280 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | DOAJ (DOAJ: Directory of Open Access Journals) |
| locations[0].source.host_organization | |
| locations[0].source.host_organization_name | |
| locations[0].license | cc-by-sa |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | article |
| locations[0].license_id | https://openalex.org/licenses/cc-by-sa |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | Logical Methods in Computer Science, Vol Volume 17, Issue 2 (2021) |
| locations[0].landing_page_url | https://doaj.org/article/fbb8e86a1b054447b57cc4d8f84f3fe0 |
| indexed_in | doaj |
| authorships[0].author.id | https://openalex.org/A5018160333 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-5620-8263 |
| authorships[0].author.display_name | Daisuke Kimura |
| authorships[0].countries | JP |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I129634264 |
| authorships[0].affiliations[0].raw_affiliation_string | Toho University, Chiba, Japan |
| authorships[0].institutions[0].id | https://openalex.org/I129634264 |
| authorships[0].institutions[0].ror | https://ror.org/02hcx7n63 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I129634264 |
| authorships[0].institutions[0].country_code | JP |
| authorships[0].institutions[0].display_name | Toho University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Daisuke Kimura |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Toho University, Chiba, Japan |
| authorships[1].author.id | https://openalex.org/A5024163301 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Makoto Tatsuta |
| authorships[1].countries | JP |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I184597095 |
| authorships[1].affiliations[0].raw_affiliation_string | National Institute of Informatics, Tokyo, Japan |
| authorships[1].institutions[0].id | https://openalex.org/I184597095 |
| authorships[1].institutions[0].ror | https://ror.org/04ksd4g47 |
| authorships[1].institutions[0].type | facility |
| authorships[1].institutions[0].lineage | https://openalex.org/I1319490839, https://openalex.org/I184597095, https://openalex.org/I4210158934 |
| authorships[1].institutions[0].country_code | JP |
| authorships[1].institutions[0].display_name | National Institute of Informatics |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Makoto Tatsuta |
| authorships[1].is_corresponding | True |
| authorships[1].raw_affiliation_strings | National Institute of Informatics, Tokyo, Japan |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://doaj.org/article/fbb8e86a1b054447b57cc4d8f84f3fe0 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Decidability for Entailments of Symbolic Heaps with Arrays |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10126 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998000264167786 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Logic, programming, and type systems |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W2972379433, https://openalex.org/W2331020993, https://openalex.org/W4383764068, https://openalex.org/W1481826604, https://openalex.org/W1797057780, https://openalex.org/W3187762542, https://openalex.org/W2583753471 |
| cited_by_count | 2 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 2 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:doaj.org/article:fbb8e86a1b054447b57cc4d8f84f3fe0 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306401280 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | DOAJ (DOAJ: Directory of Open Access Journals) |
| best_oa_location.source.host_organization | |
| best_oa_location.source.host_organization_name | |
| best_oa_location.license | cc-by-sa |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by-sa |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | Logical Methods in Computer Science, Vol Volume 17, Issue 2 (2021) |
| best_oa_location.landing_page_url | https://doaj.org/article/fbb8e86a1b054447b57cc4d8f84f3fe0 |
| primary_location.id | pmh:oai:doaj.org/article:fbb8e86a1b054447b57cc4d8f84f3fe0 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306401280 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | DOAJ (DOAJ: Directory of Open Access Journals) |
| primary_location.source.host_organization | |
| primary_location.source.host_organization_name | |
| primary_location.license | cc-by-sa |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | article |
| primary_location.license_id | https://openalex.org/licenses/cc-by-sa |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | Logical Methods in Computer Science, Vol Volume 17, Issue 2 (2021) |
| primary_location.landing_page_url | https://doaj.org/article/fbb8e86a1b054447b57cc4d8f84f3fe0 |
| publication_date | 2021-05-01 |
| publication_year | 2021 |
| referenced_works | https://openalex.org/W2130162474, https://openalex.org/W135237429, https://openalex.org/W2170612356, https://openalex.org/W1887332367, https://openalex.org/W2962831873, https://openalex.org/W2395497157, https://openalex.org/W2108611287, https://openalex.org/W1580779595, https://openalex.org/W1992012690, https://openalex.org/W134837158, https://openalex.org/W1757770995, https://openalex.org/W1506554338, https://openalex.org/W2964228214, https://openalex.org/W1511737804, https://openalex.org/W3023397123, https://openalex.org/W122465024, https://openalex.org/W2137628566, https://openalex.org/W1910824881, https://openalex.org/W1503421880, https://openalex.org/W2103490167 |
| referenced_works_count | 20 |
| abstract_inverted_index.a | 29, 84, 94, 106 |
| abstract_inverted_index.an | 88 |
| abstract_inverted_index.as | 134, 136 |
| abstract_inverted_index.by | 65, 124 |
| abstract_inverted_index.et | 67, 126 |
| abstract_inverted_index.in | 16, 51, 69, 96, 128 |
| abstract_inverted_index.is | 27, 42, 60, 83, 102, 116 |
| abstract_inverted_index.of | 13, 38, 49, 73, 90 |
| abstract_inverted_index.on | 6 |
| abstract_inverted_index.to | 117, 130 |
| abstract_inverted_index.The | 24, 36, 80, 99, 113 |
| abstract_inverted_index.al. | 68, 127 |
| abstract_inverted_index.and | 22, 33, 71, 111, 132 |
| abstract_inverted_index.are | 54 |
| abstract_inverted_index.for | 11, 28, 105 |
| abstract_inverted_index.key | 114 |
| abstract_inverted_index.not | 55, 76 |
| abstract_inverted_index.one | 72 |
| abstract_inverted_index.the | 7, 39, 45, 52, 78, 103, 119 |
| abstract_inverted_index.two | 3 |
| abstract_inverted_index.2005 | 129 |
| abstract_inverted_index.2017 | 70 |
| abstract_inverted_index.This | 0, 58 |
| abstract_inverted_index.both | 109 |
| abstract_inverted_index.does | 75 |
| abstract_inverted_index.from | 62, 87 |
| abstract_inverted_index.idea | 82, 115 |
| abstract_inverted_index.into | 93 |
| abstract_inverted_index.main | 81 |
| abstract_inverted_index.that | 47, 63 |
| abstract_inverted_index.them | 74 |
| abstract_inverted_index.well | 135 |
| abstract_inverted_index.with | 19, 31, 108 |
| abstract_inverted_index.first | 25 |
| abstract_inverted_index.heaps | 15, 92 |
| abstract_inverted_index.imply | 77 |
| abstract_inverted_index.logic | 18 |
| abstract_inverted_index.novel | 85 |
| abstract_inverted_index.paper | 1 |
| abstract_inverted_index.sizes | 48 |
| abstract_inverted_index.under | 44 |
| abstract_inverted_index.arrays | 32, 50, 110, 131 |
| abstract_inverted_index.extend | 118 |
| abstract_inverted_index.lists. | 112, 138 |
| abstract_inverted_index.other. | 79 |
| abstract_inverted_index.proved | 43 |
| abstract_inverted_index.result | 26, 101 |
| abstract_inverted_index.second | 100 |
| abstract_inverted_index.system | 30, 107 |
| abstract_inverted_index.unroll | 120 |
| abstract_inverted_index.Berdine | 125 |
| abstract_inverted_index.arrays. | 23 |
| abstract_inverted_index.formula | 95 |
| abstract_inverted_index.problem | 10 |
| abstract_inverted_index.results | 5 |
| abstract_inverted_index.checking | 9 |
| abstract_inverted_index.collapse | 121 |
| abstract_inverted_index.decision | 40 |
| abstract_inverted_index.presents | 2 |
| abstract_inverted_index.proposed | 64, 123 |
| abstract_inverted_index.symbolic | 14, 91 |
| abstract_inverted_index.validity | 8 |
| abstract_inverted_index.condition | 46, 59 |
| abstract_inverted_index.different | 61 |
| abstract_inverted_index.procedure | 41 |
| abstract_inverted_index.succedent | 53 |
| abstract_inverted_index.technique | 122 |
| abstract_inverted_index.Presburger | 20, 97 |
| abstract_inverted_index.arithmetic | 21, 133 |
| abstract_inverted_index.entailment | 89 |
| abstract_inverted_index.separation | 17 |
| abstract_inverted_index.Brotherston | 66 |
| abstract_inverted_index.arithmetic. | 98 |
| abstract_inverted_index.correctness | 37 |
| abstract_inverted_index.entailments | 12 |
| abstract_inverted_index.existential | 34 |
| abstract_inverted_index.quantified. | 57 |
| abstract_inverted_index.translation | 86 |
| abstract_inverted_index.decidability | 4, 104 |
| abstract_inverted_index.quantifiers. | 35 |
| abstract_inverted_index.double-linked | 137 |
| abstract_inverted_index.existentially | 56 |
| cited_by_percentile_year.max | 97 |
| cited_by_percentile_year.min | 95 |
| corresponding_author_ids | https://openalex.org/A5024163301 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 2 |
| corresponding_institution_ids | https://openalex.org/I184597095 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/16 |
| sustainable_development_goals[0].score | 0.8299999833106995 |
| sustainable_development_goals[0].display_name | Peace, Justice and strong institutions |
| citation_normalized_percentile.value | 0.06376857 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |