Running programs backwards: The logical inversion of imperative computation View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1997-05

AUTHORS

Brian J. Ross

ABSTRACT

Imperative programs can be inverted directly from their forward-directed program code with the use of logical inference. The relational semantics of imperative computations treats programs as logical relations over the observable state of the environment, which is taken to be the state of the variables in memory. Program relations denote both forward and backward computations, and the direction of the computation depends upon the instantiation pattern of arguments in the relation. This view of inversion has practical applications when the relational semantics is treated as a logic program. Depending on the logic programming inference scheme used, execution of this relational program can compute the inverse of the imperative program. A number of nontrivial imperative computations can be inverted with minimal logic programming tools. More... »

PAGES

331-348

References to SciGraph publications

  • 1981. The Science of Programming in NONE
  • 1982. Program Inversion in SELECTED WRITINGS ON COMPUTING: A PERSONAL PERSPECTIVE
  • 1987. Foundations of Logic Programming in NONE
  • 1987. Programming in Prolog in NONE
  • 1982-12. The thermodynamics of computation—a review in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 1991-06. Grammar-related transformations of logic programs in NEW GENERATION COMPUTING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01211087

    DOI

    http://dx.doi.org/10.1007/bf01211087

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Brock University, L2S 3A1, St Catharines, Ontario, Canada", 
              "id": "http://www.grid.ac/institutes/grid.411793.9", 
              "name": [
                "Department of Computer Science, Brock University, L2S 3A1, St Catharines, Ontario, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ross", 
            "givenName": "Brian J.", 
            "id": "sg:person.015634000213.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015634000213.70"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02084158", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014354438", 
              "https://doi.org/10.1007/bf02084158"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-5695-3_63", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006993556", 
              "https://doi.org/10.1007/978-1-4612-5695-3_63"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-97005-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013835304", 
              "https://doi.org/10.1007/978-3-642-97005-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-5983-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045860299", 
              "https://doi.org/10.1007/978-1-4612-5983-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03037639", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029425324", 
              "https://doi.org/10.1007/bf03037639"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-83189-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016029570", 
              "https://doi.org/10.1007/978-3-642-83189-8"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1997-05", 
        "datePublishedReg": "1997-05-01", 
        "description": "Imperative programs can be inverted directly from their forward-directed program code with the use of logical inference. The relational semantics of imperative computations treats programs as logical relations over the observable state of the environment, which is taken to be the state of the variables in memory. Program relations denote both forward and backward computations, and the direction of the computation depends upon the instantiation pattern of arguments in the relation. This view of inversion has practical applications when the relational semantics is treated as a logic program. Depending on the logic programming inference scheme used, execution of this relational program can compute the inverse of the imperative program. A number of nontrivial imperative computations can be inverted with minimal logic programming tools.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01211087", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136737", 
            "issn": [
              "0934-5043", 
              "1433-299X"
            ], 
            "name": "Formal Aspects of Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "9"
          }
        ], 
        "keywords": [
          "imperative computation", 
          "imperative programs", 
          "logic programming tool", 
          "relational semantics", 
          "programming tools", 
          "program code", 
          "program relations", 
          "backward computation", 
          "instantiation patterns", 
          "relational program", 
          "logic programs", 
          "inference scheme", 
          "logical inference", 
          "semantics", 
          "computation", 
          "logical relations", 
          "observable states", 
          "practical applications", 
          "logical inversion", 
          "execution", 
          "code", 
          "scheme", 
          "environment", 
          "tool", 
          "applications", 
          "program", 
          "inference", 
          "memory", 
          "view", 
          "state", 
          "inverse", 
          "number", 
          "use", 
          "direction", 
          "inversion", 
          "relation", 
          "patterns", 
          "variables", 
          "argument", 
          "treat programs", 
          "imperative computations treats programs", 
          "computations treats programs", 
          "view of inversion", 
          "logic programming inference scheme", 
          "programming inference scheme", 
          "nontrivial imperative computations", 
          "minimal logic programming tools"
        ], 
        "name": "Running programs backwards: The logical inversion of imperative computation", 
        "pagination": "331-348", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1008568428"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01211087"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01211087", 
          "https://app.dimensions.ai/details/publication/pub.1008568428"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:10", 
        "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/article/article_277.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01211087"
      }
    ]
     

    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/bf01211087'

    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/bf01211087'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    133 TRIPLES      22 PREDICATES      80 URIs      65 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01211087 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 anzsrc-for:0803
    4 schema:author Nad94ab889e60404387a91ceb53f250f4
    5 schema:citation sg:pub.10.1007/978-1-4612-5695-3_63
    6 sg:pub.10.1007/978-1-4612-5983-1
    7 sg:pub.10.1007/978-3-642-83189-8
    8 sg:pub.10.1007/978-3-642-97005-4
    9 sg:pub.10.1007/bf02084158
    10 sg:pub.10.1007/bf03037639
    11 schema:datePublished 1997-05
    12 schema:datePublishedReg 1997-05-01
    13 schema:description Imperative programs can be inverted directly from their forward-directed program code with the use of logical inference. The relational semantics of imperative computations treats programs as logical relations over the observable state of the environment, which is taken to be the state of the variables in memory. Program relations denote both forward and backward computations, and the direction of the computation depends upon the instantiation pattern of arguments in the relation. This view of inversion has practical applications when the relational semantics is treated as a logic program. Depending on the logic programming inference scheme used, execution of this relational program can compute the inverse of the imperative program. A number of nontrivial imperative computations can be inverted with minimal logic programming tools.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf N1425b0d81d2f4cc1afd9d6dd59f66f90
    18 N5eb64cf90da9406a870203ab89d55412
    19 sg:journal.1136737
    20 schema:keywords applications
    21 argument
    22 backward computation
    23 code
    24 computation
    25 computations treats programs
    26 direction
    27 environment
    28 execution
    29 imperative computation
    30 imperative computations treats programs
    31 imperative programs
    32 inference
    33 inference scheme
    34 instantiation patterns
    35 inverse
    36 inversion
    37 logic programming inference scheme
    38 logic programming tool
    39 logic programs
    40 logical inference
    41 logical inversion
    42 logical relations
    43 memory
    44 minimal logic programming tools
    45 nontrivial imperative computations
    46 number
    47 observable states
    48 patterns
    49 practical applications
    50 program
    51 program code
    52 program relations
    53 programming inference scheme
    54 programming tools
    55 relation
    56 relational program
    57 relational semantics
    58 scheme
    59 semantics
    60 state
    61 tool
    62 treat programs
    63 use
    64 variables
    65 view
    66 view of inversion
    67 schema:name Running programs backwards: The logical inversion of imperative computation
    68 schema:pagination 331-348
    69 schema:productId N410e2c62c3494d01b6bd9f4d4e90d5d0
    70 Nfb4f38a84ed44108a95662f5be62bf6c
    71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008568428
    72 https://doi.org/10.1007/bf01211087
    73 schema:sdDatePublished 2021-12-01T19:10
    74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    75 schema:sdPublisher Nb3837c74450f46ae982ebfdfbf69f50e
    76 schema:url https://doi.org/10.1007/bf01211087
    77 sgo:license sg:explorer/license/
    78 sgo:sdDataset articles
    79 rdf:type schema:ScholarlyArticle
    80 N1425b0d81d2f4cc1afd9d6dd59f66f90 schema:issueNumber 3
    81 rdf:type schema:PublicationIssue
    82 N410e2c62c3494d01b6bd9f4d4e90d5d0 schema:name dimensions_id
    83 schema:value pub.1008568428
    84 rdf:type schema:PropertyValue
    85 N5eb64cf90da9406a870203ab89d55412 schema:volumeNumber 9
    86 rdf:type schema:PublicationVolume
    87 Nad94ab889e60404387a91ceb53f250f4 rdf:first sg:person.015634000213.70
    88 rdf:rest rdf:nil
    89 Nb3837c74450f46ae982ebfdfbf69f50e schema:name Springer Nature - SN SciGraph project
    90 rdf:type schema:Organization
    91 Nfb4f38a84ed44108a95662f5be62bf6c schema:name doi
    92 schema:value 10.1007/bf01211087
    93 rdf:type schema:PropertyValue
    94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Information and Computing Sciences
    96 rdf:type schema:DefinedTerm
    97 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Computation Theory and Mathematics
    99 rdf:type schema:DefinedTerm
    100 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Computer Software
    102 rdf:type schema:DefinedTerm
    103 sg:journal.1136737 schema:issn 0934-5043
    104 1433-299X
    105 schema:name Formal Aspects of Computing
    106 schema:publisher Springer Nature
    107 rdf:type schema:Periodical
    108 sg:person.015634000213.70 schema:affiliation grid-institutes:grid.411793.9
    109 schema:familyName Ross
    110 schema:givenName Brian J.
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015634000213.70
    112 rdf:type schema:Person
    113 sg:pub.10.1007/978-1-4612-5695-3_63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006993556
    114 https://doi.org/10.1007/978-1-4612-5695-3_63
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/978-1-4612-5983-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045860299
    117 https://doi.org/10.1007/978-1-4612-5983-1
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/978-3-642-83189-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016029570
    120 https://doi.org/10.1007/978-3-642-83189-8
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-3-642-97005-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013835304
    123 https://doi.org/10.1007/978-3-642-97005-4
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/bf02084158 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014354438
    126 https://doi.org/10.1007/bf02084158
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/bf03037639 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029425324
    129 https://doi.org/10.1007/bf03037639
    130 rdf:type schema:CreativeWork
    131 grid-institutes:grid.411793.9 schema:alternateName Department of Computer Science, Brock University, L2S 3A1, St Catharines, Ontario, Canada
    132 schema:name Department of Computer Science, Brock University, L2S 3A1, St Catharines, Ontario, Canada
    133 rdf:type schema:Organization
     




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


    ...