View in EDS

Termination proofs for linear simple loops.

Saved in:
Bibliographic Details
Title: Termination proofs for linear simple loops.
Authors: Chen, Hong1 hchen11@lsu.edu, Flur, Shaked2 fshaked@cs.technion.ac.il, Mukhopadhyay, Supratik1 supratik@csc.lsu.edu
Source: International Journal on Software Tools for Technology Transfer. Feb2015, Vol. 17 Issue 1, p47-57. 11p.
Subjects: Loops (Group theory), Computer software termination, Computer programming, Lexicography, Polynomials
Abstract: Analysis of termination and other liveness properties of a program can be reduced to termination proof synthesis for simple loops, i.e., loops with only variable updates in the loop body. Among simple loops, the subset of linear simple loops (LSLs) is particularly interesting because it is common in practice and expressive in theory. Existing techniques can successfully synthesize a linear ranking function for an LSL if there exists one. However, when a terminating LSL does not have a linear ranking function, these techniques fail. In this paper, we describe an automatic method that generates proofs of (universal) termination for LSLs based on the synthesis of disjunctive ranking relations. The method repeatedly finds linear ranking functions on partitions of the state space and checks whether the transitive closure of the transition relation is included in the union of the ranking relations. Our method extends the work of Podelski and Rybalchenko (A complete method for the synthesis of linear ranking functions. In: Proceedings of the 5th international conference on VMCAI, Jan 2004, Venice, Italy, pp 239-251, ). We have implemented a prototype of the method and have shown experimental evidence of the effectiveness of our method. [ABSTRACT FROM AUTHOR]
Copyright of International Journal on Software Tools for Technology Transfer is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 100550344
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Termination proofs for linear simple loops.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Chen%2C+Hong%22">Chen, Hong</searchLink><relatesTo>1</relatesTo><i> hchen11@lsu.edu</i><br /><searchLink fieldCode="AR" term="%22Flur%2C+Shaked%22">Flur, Shaked</searchLink><relatesTo>2</relatesTo><i> fshaked@cs.technion.ac.il</i><br /><searchLink fieldCode="AR" term="%22Mukhopadhyay%2C+Supratik%22">Mukhopadhyay, Supratik</searchLink><relatesTo>1</relatesTo><i> supratik@csc.lsu.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22International+Journal+on+Software+Tools+for+Technology+Transfer%22">International Journal on Software Tools for Technology Transfer</searchLink>. Feb2015, Vol. 17 Issue 1, p47-57. 11p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Loops+%28Group+theory%29%22">Loops (Group theory)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software+termination%22">Computer software termination</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+programming%22">Computer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Lexicography%22">Lexicography</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Analysis of termination and other liveness properties of a program can be reduced to termination proof synthesis for simple loops, i.e., loops with only variable updates in the loop body. Among simple loops, the subset of linear simple loops (LSLs) is particularly interesting because it is common in practice and expressive in theory. Existing techniques can successfully synthesize a linear ranking function for an LSL if there exists one. However, when a terminating LSL does not have a linear ranking function, these techniques fail. In this paper, we describe an automatic method that generates proofs of (universal) termination for LSLs based on the synthesis of disjunctive ranking relations. The method repeatedly finds linear ranking functions on partitions of the state space and checks whether the transitive closure of the transition relation is included in the union of the ranking relations. Our method extends the work of Podelski and Rybalchenko (A complete method for the synthesis of linear ranking functions. In: Proceedings of the 5th international conference on VMCAI, Jan 2004, Venice, Italy, pp 239-251, ). We have implemented a prototype of the method and have shown experimental evidence of the effectiveness of our method. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of International Journal on Software Tools for Technology Transfer is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=100550344
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s10009-013-0288-8
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 11
        StartPage: 47
    Subjects:
      – SubjectFull: Loops (Group theory)
        Type: general
      – SubjectFull: Computer software termination
        Type: general
      – SubjectFull: Computer programming
        Type: general
      – SubjectFull: Lexicography
        Type: general
      – SubjectFull: Polynomials
        Type: general
    Titles:
      – TitleFull: Termination proofs for linear simple loops.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Chen, Hong
      – PersonEntity:
          Name:
            NameFull: Flur, Shaked
      – PersonEntity:
          Name:
            NameFull: Mukhopadhyay, Supratik
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: Feb2015
              Type: published
              Y: 2015
          Identifiers:
            – Type: issn-print
              Value: 14332779
          Numbering:
            – Type: volume
              Value: 17
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: International Journal on Software Tools for Technology Transfer
              Type: main
ResultId 1