Defining Fair Merge as a Colimit: Towards a Fixed-Point Theory for Indeterminate Dataflow View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1990

AUTHORS

Marta Zofia Kwiatkowska , Michael William Shields , Richard Monro Thomas , David B. Benson , Prakash Panangaden , James R. Russell

ABSTRACT

We define the action of the indeterminate dataflow primitive, fair merge, on infinite inputs as a limit. Fair merge is known to embody unbounded indeterminacy and is hence not continuous. Recent results about the expressiveness of indeterminate primitives shows that it is not even monotone in a suitable sense. Given this it is rather surprising that one can give a limiting description of fair merge. The key idea is to define fair merge in terms of the limit of a sequence of “tests”. The approach is suggested by an algebraic theory of distributed computing based on the notion of a bimonoid or bialgebra. More... »

PAGES

175-184

References to SciGraph publications

  • 1988. Computations, residuals, and the power of indeterminacy in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1982. A powerdomain for countable non-determinism in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1988. McCarthy's amb cannot implement fair merge in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 1988. The shuffle bialgebra in MATHEMATICAL FOUNDATIONS OF PROGRAMMING LANGUAGE SEMANTICS
  • 1983. On semantic foundations for applicative multiprogramming in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1981. Scenarios: A model of non-determinate computation in FORMALIZATION OF PROGRAMMING CONCEPTS
  • Book

    TITLE

    Semantics for Concurrency

    ISBN

    978-3-540-19625-9
    978-1-4471-3860-0

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-1-4471-3860-0_11

    DOI

    http://dx.doi.org/10.1007/978-1-4471-3860-0_11

    DIMENSIONS

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


    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/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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "familyName": "Kwiatkowska", 
            "givenName": "Marta Zofia", 
            "id": "sg:person.011375012273.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39"
            ], 
            "type": "Person"
          }, 
          {
            "familyName": "Shields", 
            "givenName": "Michael William", 
            "id": "sg:person.07465425675.46", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07465425675.46"
            ], 
            "type": "Person"
          }, 
          {
            "familyName": "Thomas", 
            "givenName": "Richard Monro", 
            "id": "sg:person.013217343010.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013217343010.08"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Washington State University", 
              "id": "https://www.grid.ac/institutes/grid.30064.31", 
              "name": [
                "Computer Science Department, Washington State University, Pullman, Washington\u00a099164-1210, USA"
              ], 
              "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"
          }, 
          {
            "affiliation": {
              "alternateName": "Cornell University", 
              "id": "https://www.grid.ac/institutes/grid.5386.8", 
              "name": [
                "Department of Computer Science, Cornell University, Ithaca, NY\u00a014853, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Panangaden", 
            "givenName": "Prakash", 
            "id": "sg:person.01233076234.42", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01233076234.42"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Cornell University", 
              "id": "https://www.grid.ac/institutes/grid.5386.8", 
              "name": [
                "Department of Computer Science, Cornell University, Ithaca, NY\u00a014853, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Russell", 
            "givenName": "James R.", 
            "id": "sg:person.010256000716.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010256000716.40"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/44501.44504", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012584021"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-50517-2_90", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017278735", 
              "https://doi.org/10.1007/3-540-50517-2_90"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-10699-5_102", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022051712", 
              "https://doi.org/10.1007/3-540-10699-5_102"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-19020-1_32", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029289346", 
              "https://doi.org/10.1007/3-540-19020-1_32"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(87)90045-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030539676"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/6490.6494", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030783677"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(78)90048-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031092667"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0036893", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032111831", 
              "https://doi.org/10.1007/bfb0036893"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0012788", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037436695", 
              "https://doi.org/10.1007/bfb0012788"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/96709.96742", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037613920"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(84)80032-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048951992"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-19488-6_133", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049700871", 
              "https://doi.org/10.1007/3-540-19488-6_133"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/lics.1989.39172", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086199793"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1990", 
        "datePublishedReg": "1990-01-01", 
        "description": "We define the action of the indeterminate dataflow primitive, fair merge, on infinite inputs as a limit. Fair merge is known to embody unbounded indeterminacy and is hence not continuous. Recent results about the expressiveness of indeterminate primitives shows that it is not even monotone in a suitable sense. Given this it is rather surprising that one can give a limiting description of fair merge. The key idea is to define fair merge in terms of the limit of a sequence of \u201ctests\u201d. The approach is suggested by an algebraic theory of distributed computing based on the notion of a bimonoid or bialgebra.", 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-1-4471-3860-0_11", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3363317", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.3368894", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-540-19625-9", 
            "978-1-4471-3860-0"
          ], 
          "name": "Semantics for Concurrency", 
          "type": "Book"
        }, 
        "name": "Defining Fair Merge as a Colimit: Towards a Fixed-Point Theory for Indeterminate Dataflow", 
        "pagination": "175-184", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-1-4471-3860-0_11"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "4b4e26e0f5879f04d0edca88791d019310c326f37d0a414519970f8d1e9fe712"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1015804671"
            ]
          }
        ], 
        "publisher": {
          "location": "London", 
          "name": "Springer London", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-1-4471-3860-0_11", 
          "https://app.dimensions.ai/details/publication/pub.1015804671"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T21:01", 
        "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_8690_00000253.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-1-4471-3860-0_11"
      }
    ]
     

    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/978-1-4471-3860-0_11'

    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/978-1-4471-3860-0_11'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4471-3860-0_11'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4471-3860-0_11'


     

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

    143 TRIPLES      22 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-1-4471-3860-0_11 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nd4d0b9551bf248c3a413e69bab5efa2c
    4 schema:citation sg:pub.10.1007/3-540-10699-5_102
    5 sg:pub.10.1007/3-540-19020-1_32
    6 sg:pub.10.1007/3-540-19488-6_133
    7 sg:pub.10.1007/3-540-50517-2_90
    8 sg:pub.10.1007/bfb0012788
    9 sg:pub.10.1007/bfb0036893
    10 https://doi.org/10.1016/0022-0000(78)90048-x
    11 https://doi.org/10.1016/0304-3975(87)90045-4
    12 https://doi.org/10.1016/s0019-9958(84)80032-7
    13 https://doi.org/10.1109/lics.1989.39172
    14 https://doi.org/10.1145/44501.44504
    15 https://doi.org/10.1145/6490.6494
    16 https://doi.org/10.1145/96709.96742
    17 schema:datePublished 1990
    18 schema:datePublishedReg 1990-01-01
    19 schema:description We define the action of the indeterminate dataflow primitive, fair merge, on infinite inputs as a limit. Fair merge is known to embody unbounded indeterminacy and is hence not continuous. Recent results about the expressiveness of indeterminate primitives shows that it is not even monotone in a suitable sense. Given this it is rather surprising that one can give a limiting description of fair merge. The key idea is to define fair merge in terms of the limit of a sequence of “tests”. The approach is suggested by an algebraic theory of distributed computing based on the notion of a bimonoid or bialgebra.
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N387e316d535d4aae9baf719d0c391bdc
    24 schema:name Defining Fair Merge as a Colimit: Towards a Fixed-Point Theory for Indeterminate Dataflow
    25 schema:pagination 175-184
    26 schema:productId N2839802edbe94d9d830189f52c453c43
    27 N2d47e162b3254805a65891089e9e8035
    28 N7ff57e9eb57e49ef9de641a98e088188
    29 schema:publisher Nde037092ebac4901afe065960e069289
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015804671
    31 https://doi.org/10.1007/978-1-4471-3860-0_11
    32 schema:sdDatePublished 2019-04-15T21:01
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N6ead3c0774ec40f18e579dffcf01c462
    35 schema:url http://link.springer.com/10.1007/978-1-4471-3860-0_11
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N2180b9ab79d148e58575f61c49870d84 rdf:first sg:person.015006706745.00
    40 rdf:rest Nbd1639c18acb49e8af7b947d7337eeab
    41 N25394c51a5be4d1387e02b708db1814e rdf:first sg:person.07465425675.46
    42 rdf:rest N57afabfea42e4ae88eb5a50d05a11fbd
    43 N2839802edbe94d9d830189f52c453c43 schema:name dimensions_id
    44 schema:value pub.1015804671
    45 rdf:type schema:PropertyValue
    46 N2d47e162b3254805a65891089e9e8035 schema:name doi
    47 schema:value 10.1007/978-1-4471-3860-0_11
    48 rdf:type schema:PropertyValue
    49 N387e316d535d4aae9baf719d0c391bdc schema:isbn 978-1-4471-3860-0
    50 978-3-540-19625-9
    51 schema:name Semantics for Concurrency
    52 rdf:type schema:Book
    53 N57afabfea42e4ae88eb5a50d05a11fbd rdf:first sg:person.013217343010.08
    54 rdf:rest N2180b9ab79d148e58575f61c49870d84
    55 N6ead3c0774ec40f18e579dffcf01c462 schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 N7ff57e9eb57e49ef9de641a98e088188 schema:name readcube_id
    58 schema:value 4b4e26e0f5879f04d0edca88791d019310c326f37d0a414519970f8d1e9fe712
    59 rdf:type schema:PropertyValue
    60 Nbd1639c18acb49e8af7b947d7337eeab rdf:first sg:person.01233076234.42
    61 rdf:rest Nf88bede224724dc28eb0f242fd4bc22d
    62 Nd4d0b9551bf248c3a413e69bab5efa2c rdf:first sg:person.011375012273.39
    63 rdf:rest N25394c51a5be4d1387e02b708db1814e
    64 Nde037092ebac4901afe065960e069289 schema:location London
    65 schema:name Springer London
    66 rdf:type schema:Organisation
    67 Nf88bede224724dc28eb0f242fd4bc22d rdf:first sg:person.010256000716.40
    68 rdf:rest rdf:nil
    69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Information and Computing Sciences
    71 rdf:type schema:DefinedTerm
    72 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Computation Theory and Mathematics
    74 rdf:type schema:DefinedTerm
    75 sg:grant.3363317 http://pending.schema.org/fundedItem sg:pub.10.1007/978-1-4471-3860-0_11
    76 rdf:type schema:MonetaryGrant
    77 sg:grant.3368894 http://pending.schema.org/fundedItem sg:pub.10.1007/978-1-4471-3860-0_11
    78 rdf:type schema:MonetaryGrant
    79 sg:person.010256000716.40 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
    80 schema:familyName Russell
    81 schema:givenName James R.
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010256000716.40
    83 rdf:type schema:Person
    84 sg:person.011375012273.39 schema:familyName Kwiatkowska
    85 schema:givenName Marta Zofia
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39
    87 rdf:type schema:Person
    88 sg:person.01233076234.42 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
    89 schema:familyName Panangaden
    90 schema:givenName Prakash
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01233076234.42
    92 rdf:type schema:Person
    93 sg:person.013217343010.08 schema:familyName Thomas
    94 schema:givenName Richard Monro
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013217343010.08
    96 rdf:type schema:Person
    97 sg:person.015006706745.00 schema:affiliation https://www.grid.ac/institutes/grid.30064.31
    98 schema:familyName Benson
    99 schema:givenName David B.
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015006706745.00
    101 rdf:type schema:Person
    102 sg:person.07465425675.46 schema:familyName Shields
    103 schema:givenName Michael William
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07465425675.46
    105 rdf:type schema:Person
    106 sg:pub.10.1007/3-540-10699-5_102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022051712
    107 https://doi.org/10.1007/3-540-10699-5_102
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/3-540-19020-1_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029289346
    110 https://doi.org/10.1007/3-540-19020-1_32
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/3-540-19488-6_133 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049700871
    113 https://doi.org/10.1007/3-540-19488-6_133
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/3-540-50517-2_90 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017278735
    116 https://doi.org/10.1007/3-540-50517-2_90
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/bfb0012788 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037436695
    119 https://doi.org/10.1007/bfb0012788
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/bfb0036893 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032111831
    122 https://doi.org/10.1007/bfb0036893
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1016/0022-0000(78)90048-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1031092667
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1016/0304-3975(87)90045-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030539676
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1016/s0019-9958(84)80032-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048951992
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1109/lics.1989.39172 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086199793
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1145/44501.44504 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012584021
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1145/6490.6494 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030783677
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1145/96709.96742 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037613920
    137 rdf:type schema:CreativeWork
    138 https://www.grid.ac/institutes/grid.30064.31 schema:alternateName Washington State University
    139 schema:name Computer Science Department, Washington State University, Pullman, Washington 99164-1210, USA
    140 rdf:type schema:Organization
    141 https://www.grid.ac/institutes/grid.5386.8 schema:alternateName Cornell University
    142 schema:name Department of Computer Science, Cornell University, Ithaca, NY 14853, USA
    143 rdf:type schema:Organization
     




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


    ...