2 Search Results for "Kimura, Daisuke"

Document

DOI: 10.4230/LIPIcs.FSCD.2024.18

Representation of Peano Arithmetic in Separation Logic

Authors: Sohei Ito and Makoto Tatsuta

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)

Abstract

Separation logic is successful for software verification of heap-manipulating programs. Numbers are necessary to be added to separation logic for verification of practical software where numbers are important. However, properties of the validity such as decidability and complexity for separation logic with numbers have not been fully studied yet. This paper presents the translation of Pi-0-1 formulas in Peano arithmetic to formulas in a small fragment of separation logic with numbers, which consists only of the intuitionistic points-to predicate, 0 and the successor function. Then this paper proves that a formula in Peano arithmetic is valid in the standard model if and only if its translation in this fragment is valid in the standard interpretation. As a corollary, this paper also gives a perspective proof for the undecidability of the validity in this fragment. Since Pi-0-1 formulas can describe consistency of logical systems and non-termination of computations, this result also shows that these properties discussed in Peano arithmetic can also be discussed in such a small fragment of separation logic with numbers.

Cite as

Sohei Ito and Makoto Tatsuta. Representation of Peano Arithmetic in Separation Logic. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.FSCD.2024.18,
  author =	{Ito, Sohei and Tatsuta, Makoto},
  title =	{{Representation of Peano Arithmetic in Separation Logic}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.18},
  URN =		{urn:nbn:de:0030-drops-203476},
  doi =		{10.4230/LIPIcs.FSCD.2024.18},
  annote =	{Keywords: First order logic, Separation logic, Peano arithmetic, Presburger arithmetic}
}

Document

DOI: 10.4230/LIPIcs.FSCD.2021.11

Failure of Cut-Elimination in the Cyclic Proof System of Bunched Logic with Inductive Propositions

Authors: Kenji Saotome, Koji Nakazawa, and Daisuke Kimura

Published in: LIPIcs, Volume 195, 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)

Abstract

Cyclic proof systems are sequent-calculus style proof systems that allow circular structures representing induction, and they are considered suitable for automated inductive reasoning. However, Kimura et al. have shown that the cyclic proof system for the symbolic heap separation logic does not satisfy the cut-elimination property, one of the most fundamental properties of proof systems. This paper proves that the cyclic proof system for the bunched logic with only nullary inductive predicates does not satisfy the cut-elimination property. It is hard to adapt the existing proof technique chasing contradictory paths in cyclic proofs since the bunched logic contains the structural rules. This paper proposes a new proof technique called proof unrolling. This technique can be adapted to the symbolic heap separation logic, and it shows that the cut-elimination fails even if we restrict the inductive predicates to nullary ones.

Cite as

Kenji Saotome, Koji Nakazawa, and Daisuke Kimura. Failure of Cut-Elimination in the Cyclic Proof System of Bunched Logic with Inductive Propositions. In 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 195, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{saotome_et_al:LIPIcs.FSCD.2021.11,
  author =	{Saotome, Kenji and Nakazawa, Koji and Kimura, Daisuke},
  title =	{{Failure of Cut-Elimination in the Cyclic Proof System of Bunched Logic with Inductive Propositions}},
  booktitle =	{6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-191-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{195},
  editor =	{Kobayashi, Naoki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2021.11},
  URN =		{urn:nbn:de:0030-drops-142494},
  doi =		{10.4230/LIPIcs.FSCD.2021.11},
  annote =	{Keywords: cyclic proofs, cut-elimination, bunched logic, separation logic, linear logic}
}

Refine by Author
1 Ito, Sohei
1 Kimura, Daisuke
1 Nakazawa, Koji
1 Saotome, Kenji
1 Tatsuta, Makoto

Refine by Classification
2 Theory of computation → Separation logic
1 Theory of computation → Proof theory

Refine by Keyword
1 First order logic
1 Peano arithmetic
1 Presburger arithmetic
1 Separation logic
1 bunched logic
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2021
1 2024