Functional behavior of nondeterministic programs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1983

AUTHORS

Michael G. Main , David B. Benson

ABSTRACT

The functional behavior of a deterministic program is a function f:D→D, where D is some set of states for the computation. This notion of functional behaviors can be extended to nondeterministic programs using techniques from linear algebra. In particular, the functional behavior of a nondeterministic program is a linear transformation f:A→A, where A is a free semiring module. Other notions from linear algebra carry over into this setting. For example, weakest preconditions and predicate transformers correspond to well-studied concepts in linear algebra. Finally, we consider multiple-input and multiple-output programs. The functional behavior of a nondeterministic program with multiple inputs and outputs is a linear transformation f:⊗ m A→⊗ n A, where ⊗ x A is an iterated tensor product of the semiring module A. This is in contrast to the deterministic case, where such a program is a function f:D m →D n , using the Cartesian products D m and D n . More... »

PAGES

290-301

Book

TITLE

Foundations of Computation Theory

ISBN

978-3-540-12689-8
978-3-540-38682-7

Author Affiliations

From Grant

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-12689-9_112

DOI

http://dx.doi.org/10.1007/3-540-12689-9_112

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Colorado Boulder", 
          "id": "https://www.grid.ac/institutes/grid.266190.a", 
          "name": [
            "Department of Computer Science, University of Colorado, 80309\u00a0Boulder, CO, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Main", 
        "givenName": "Michael G.", 
        "id": "sg:person.011150657575.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011150657575.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Computer Science, Washington State University, 99164-1210 USA\u00a0Pullman, WA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Benson", 
        "givenName": "David B.", 
        "id": "sg:person.015006706745.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015006706745.00"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1983", 
    "datePublishedReg": "1983-01-01", 
    "description": "The functional behavior of a deterministic program is a function f:D\u2192D, where D is some set of states for the computation. This notion of functional behaviors can be extended to nondeterministic programs using techniques from linear algebra. In particular, the functional behavior of a nondeterministic program is a linear transformation f:A\u2192A, where A is a free semiring module. Other notions from linear algebra carry over into this setting. For example, weakest preconditions and predicate transformers correspond to well-studied concepts in linear algebra. Finally, we consider multiple-input and multiple-output programs. The functional behavior of a nondeterministic program with multiple inputs and outputs is a linear transformation f:\u2297 m A\u2192\u2297 n A, where \u2297 x A is an iterated tensor product of the semiring module A. This is in contrast to the deterministic case, where such a program is a function f:D m \u2192D n , using the Cartesian products D m and D n .", 
    "editor": [
      {
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-12689-9_112", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3303017", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-12689-8", 
        "978-3-540-38682-7"
      ], 
      "name": "Foundations of Computation Theory", 
      "type": "Book"
    }, 
    "name": "Functional behavior of nondeterministic programs", 
    "pagination": "290-301", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-12689-9_112"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "bf6b289897a9c57420748a7e96f88a718246948c08930765ce14f1fa27389e87"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040183266"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-12689-9_112", 
      "https://app.dimensions.ai/details/publication/pub.1040183266"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T10:21", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8659_00000069.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-12689-9_112"
  }
]
 

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/3-540-12689-9_112'

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/3-540-12689-9_112'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-12689-9_112'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-12689-9_112'


 

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

76 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-12689-9_112 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Nb490d38df2e8446b8bd47abb6e0cde3f
4 schema:datePublished 1983
5 schema:datePublishedReg 1983-01-01
6 schema:description The functional behavior of a deterministic program is a function f:D→D, where D is some set of states for the computation. This notion of functional behaviors can be extended to nondeterministic programs using techniques from linear algebra. In particular, the functional behavior of a nondeterministic program is a linear transformation f:A→A, where A is a free semiring module. Other notions from linear algebra carry over into this setting. For example, weakest preconditions and predicate transformers correspond to well-studied concepts in linear algebra. Finally, we consider multiple-input and multiple-output programs. The functional behavior of a nondeterministic program with multiple inputs and outputs is a linear transformation f:⊗ m A→⊗ n A, where ⊗ x A is an iterated tensor product of the semiring module A. This is in contrast to the deterministic case, where such a program is a function f:D m →D n , using the Cartesian products D m and D n .
7 schema:editor N3ec9db6b86244614ba9afbe30341a9ca
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N69a61f560b624938b283ac655285d706
12 schema:name Functional behavior of nondeterministic programs
13 schema:pagination 290-301
14 schema:productId N74308920eb9943eba785c279b852e698
15 N92dca11fd35e4163999ccf04f3ac7597
16 Ncc14051d5fd148169ac74d97c5f9314f
17 schema:publisher N247ae2ba0d8e48b48894d4767884bf64
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040183266
19 https://doi.org/10.1007/3-540-12689-9_112
20 schema:sdDatePublished 2019-04-15T10:21
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nf7e17ef0c4494dbfa22911eae7ebd14a
23 schema:url http://link.springer.com/10.1007/3-540-12689-9_112
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N247ae2ba0d8e48b48894d4767884bf64 schema:location Berlin, Heidelberg
28 schema:name Springer Berlin Heidelberg
29 rdf:type schema:Organisation
30 N29834baf2ddb4003ac73cb6d8d4b1fb4 schema:familyName Karpinski
31 schema:givenName Marek
32 rdf:type schema:Person
33 N3ec9db6b86244614ba9afbe30341a9ca rdf:first N29834baf2ddb4003ac73cb6d8d4b1fb4
34 rdf:rest rdf:nil
35 N492ed0bef5e04b439d1922c53b9a90ff schema:name Department of Computer Science, Washington State University, 99164-1210 USA Pullman, WA
36 rdf:type schema:Organization
37 N69a61f560b624938b283ac655285d706 schema:isbn 978-3-540-12689-8
38 978-3-540-38682-7
39 schema:name Foundations of Computation Theory
40 rdf:type schema:Book
41 N74308920eb9943eba785c279b852e698 schema:name readcube_id
42 schema:value bf6b289897a9c57420748a7e96f88a718246948c08930765ce14f1fa27389e87
43 rdf:type schema:PropertyValue
44 N8b3dec3bb248443bad713c5e9a3c344a rdf:first sg:person.015006706745.00
45 rdf:rest rdf:nil
46 N92dca11fd35e4163999ccf04f3ac7597 schema:name doi
47 schema:value 10.1007/3-540-12689-9_112
48 rdf:type schema:PropertyValue
49 Nb490d38df2e8446b8bd47abb6e0cde3f rdf:first sg:person.011150657575.76
50 rdf:rest N8b3dec3bb248443bad713c5e9a3c344a
51 Ncc14051d5fd148169ac74d97c5f9314f schema:name dimensions_id
52 schema:value pub.1040183266
53 rdf:type schema:PropertyValue
54 Nf7e17ef0c4494dbfa22911eae7ebd14a schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
57 schema:name Mathematical Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
60 schema:name Statistics
61 rdf:type schema:DefinedTerm
62 sg:grant.3303017 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-12689-9_112
63 rdf:type schema:MonetaryGrant
64 sg:person.011150657575.76 schema:affiliation https://www.grid.ac/institutes/grid.266190.a
65 schema:familyName Main
66 schema:givenName Michael G.
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011150657575.76
68 rdf:type schema:Person
69 sg:person.015006706745.00 schema:affiliation N492ed0bef5e04b439d1922c53b9a90ff
70 schema:familyName Benson
71 schema:givenName David B.
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015006706745.00
73 rdf:type schema:Person
74 https://www.grid.ac/institutes/grid.266190.a schema:alternateName University of Colorado Boulder
75 schema:name Department of Computer Science, University of Colorado, 80309 Boulder, CO, USA
76 rdf:type schema:Organization
 




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


...