The monoid of queue actions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-12

AUTHORS

Martin Huschenbett, Dietrich Kuske, Georg Zetzsche

ABSTRACT

We model the behavior of a fifo-queue as a monoid of transformations that are induced by sequences of writing and reading. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties such as conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NL-complete. Furthermore, we present an algebraic characterization of this monoid’s recognizable subsets. Finally, we prove that it is not Thurston-automatic. More... »

PAGES

475-508

References to SciGraph publications

  • 2016. The Trace Monoids in the Queue Monoid and in the Direct Product of Two Free Monoids in DEVELOPMENTS IN LANGUAGE THEORY
  • 2014. The Monoid of Queue Actions in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2014
  • 1993. String-Rewriting Systems in NONE
  • 2004-12. Finite Presentations of Infinite Structures: Automata and Interpretations in THEORY OF COMPUTING SYSTEMS
  • 1979. Transductions and Context-Free Languages in NONE
  • 1995. Automatic presentations of structures in LOGIC AND COMPUTATIONAL COMPLEXITY
  • 1984-12. Conjugacy in monoids with a special Church-Rosser presentation is decidable in SEMIGROUP FORUM
  • 1986. Unique decipherability for partially commutative alphabet (extended abstract) in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1986
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00233-016-9835-4

    DOI

    http://dx.doi.org/10.1007/s00233-016-9835-4

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "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": {
              "name": [
                "London, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Huschenbett", 
            "givenName": "Martin", 
            "id": "sg:person.011075760527.69", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011075760527.69"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Ilmenau University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6553.5", 
              "name": [
                "Institut f\u00fcr Theoretische Informatik, TU Ilmenau, Ilmenau, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kuske", 
            "givenName": "Dietrich", 
            "id": "sg:person.013520370123.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013520370123.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
              "id": "https://www.grid.ac/institutes/grid.464035.0", 
              "name": [
                "LSV, CNRS & ENS Cachan, Universit\u00e9 Paris-Saclay, Cachan, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zetzsche", 
            "givenName": "Georg", 
            "id": "sg:person.014551676263.38", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014551676263.38"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-663-09367-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003958860", 
              "https://doi.org/10.1007/978-3-663-09367-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-663-09367-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003958860", 
              "https://doi.org/10.1007/978-3-663-09367-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90028-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008217602"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90028-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008217602"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-44522-8_29", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017435896", 
              "https://doi.org/10.1007/978-3-662-44522-8_29"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1018692631", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-9771-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018692631", 
              "https://doi.org/10.1007/978-1-4613-9771-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-9771-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018692631", 
              "https://doi.org/10.1007/978-1-4613-9771-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0021-8693(91)90275-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019146297"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(93)90230-q", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027432427"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0016249", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027506737", 
              "https://doi.org/10.1007/bfb0016249"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-004-1133-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029593225", 
              "https://doi.org/10.1007/s00224-004-1133-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781316227343.024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033189390"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00927870802243580", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039759685"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60178-3_93", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040488919", 
              "https://doi.org/10.1007/3-540-60178-3_93"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02573327", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040716819", 
              "https://doi.org/10.1007/bf02573327"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02573327", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040716819", 
              "https://doi.org/10.1007/bf02573327"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-53132-7_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042131935", 
              "https://doi.org/10.1007/978-3-662-53132-7_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(99)00151-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047104068"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0218196793000135", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062962050"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4171/ggd/221", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072317089"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-12", 
        "datePublishedReg": "2017-12-01", 
        "description": "We model the behavior of a fifo-queue as a monoid of transformations that are induced by sequences of writing and reading. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties such as conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NL-complete. Furthermore, we present an algebraic characterization of this monoid\u2019s recognizable subsets. Finally, we prove that it is not Thurston-automatic.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00233-016-9835-4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136094", 
            "issn": [
              "0037-1912", 
              "1432-2137"
            ], 
            "name": "Semigroup Forum", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "95"
          }
        ], 
        "name": "The monoid of queue actions", 
        "pagination": "475-508", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c222d46c2c5a0df8f1c847f6999bc55e678393663601db35328f2d2ad8e42a4b"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00233-016-9835-4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1040754113"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00233-016-9835-4", 
          "https://app.dimensions.ai/details/publication/pub.1040754113"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:35", 
        "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/0000000363_0000000363/records_70028_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00233-016-9835-4"
      }
    ]
     

    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/s00233-016-9835-4'

    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/s00233-016-9835-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00233-016-9835-4'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00233-016-9835-4'


     

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

    138 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00233-016-9835-4 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nb5a0bd36367e46a9a4c278f8d0a6bb33
    4 schema:citation sg:pub.10.1007/3-540-60178-3_93
    5 sg:pub.10.1007/978-1-4613-9771-7
    6 sg:pub.10.1007/978-3-662-44522-8_29
    7 sg:pub.10.1007/978-3-662-53132-7_21
    8 sg:pub.10.1007/978-3-663-09367-1
    9 sg:pub.10.1007/bf02573327
    10 sg:pub.10.1007/bfb0016249
    11 sg:pub.10.1007/s00224-004-1133-y
    12 https://app.dimensions.ai/details/publication/pub.1018692631
    13 https://doi.org/10.1016/0021-8693(91)90275-d
    14 https://doi.org/10.1016/0304-3975(86)90028-9
    15 https://doi.org/10.1016/0304-3975(93)90230-q
    16 https://doi.org/10.1016/s0304-3975(99)00151-6
    17 https://doi.org/10.1017/cbo9781316227343.024
    18 https://doi.org/10.1080/00927870802243580
    19 https://doi.org/10.1142/s0218196793000135
    20 https://doi.org/10.4171/ggd/221
    21 schema:datePublished 2017-12
    22 schema:datePublishedReg 2017-12-01
    23 schema:description We model the behavior of a fifo-queue as a monoid of transformations that are induced by sequences of writing and reading. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties such as conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NL-complete. Furthermore, we present an algebraic characterization of this monoid’s recognizable subsets. Finally, we prove that it is not Thurston-automatic.
    24 schema:genre research_article
    25 schema:inLanguage en
    26 schema:isAccessibleForFree false
    27 schema:isPartOf N050166eb50894a069e5452d9ef0d20dc
    28 Ne50256b05803465dbf71950303cf8608
    29 sg:journal.1136094
    30 schema:name The monoid of queue actions
    31 schema:pagination 475-508
    32 schema:productId N2b5b63b10750430099f3b46be42bf0bb
    33 Na01f6f342b4f4f3ebee5f10407d7db2a
    34 Nf1f30d1641874b4898399c5c0d76b2c6
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040754113
    36 https://doi.org/10.1007/s00233-016-9835-4
    37 schema:sdDatePublished 2019-04-11T12:35
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher N4b45c65d3cfd41b786b3fcecc1791a27
    40 schema:url https://link.springer.com/10.1007%2Fs00233-016-9835-4
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset articles
    43 rdf:type schema:ScholarlyArticle
    44 N050166eb50894a069e5452d9ef0d20dc schema:volumeNumber 95
    45 rdf:type schema:PublicationVolume
    46 N2b5b63b10750430099f3b46be42bf0bb schema:name dimensions_id
    47 schema:value pub.1040754113
    48 rdf:type schema:PropertyValue
    49 N4b45c65d3cfd41b786b3fcecc1791a27 schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 Na01f6f342b4f4f3ebee5f10407d7db2a schema:name readcube_id
    52 schema:value c222d46c2c5a0df8f1c847f6999bc55e678393663601db35328f2d2ad8e42a4b
    53 rdf:type schema:PropertyValue
    54 Nb15fdad1c88e488da12e169e83b18ef7 rdf:first sg:person.013520370123.82
    55 rdf:rest Ne0ee8dac873e46b4a508503cb9ac3ad0
    56 Nb5a0bd36367e46a9a4c278f8d0a6bb33 rdf:first sg:person.011075760527.69
    57 rdf:rest Nb15fdad1c88e488da12e169e83b18ef7
    58 Ne0ee8dac873e46b4a508503cb9ac3ad0 rdf:first sg:person.014551676263.38
    59 rdf:rest rdf:nil
    60 Ne50256b05803465dbf71950303cf8608 schema:issueNumber 3
    61 rdf:type schema:PublicationIssue
    62 Necab39bc8e254cfcadfb7c109edf41b9 schema:name London, UK
    63 rdf:type schema:Organization
    64 Nf1f30d1641874b4898399c5c0d76b2c6 schema:name doi
    65 schema:value 10.1007/s00233-016-9835-4
    66 rdf:type schema:PropertyValue
    67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Mathematical Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Pure Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:journal.1136094 schema:issn 0037-1912
    74 1432-2137
    75 schema:name Semigroup Forum
    76 rdf:type schema:Periodical
    77 sg:person.011075760527.69 schema:affiliation Necab39bc8e254cfcadfb7c109edf41b9
    78 schema:familyName Huschenbett
    79 schema:givenName Martin
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011075760527.69
    81 rdf:type schema:Person
    82 sg:person.013520370123.82 schema:affiliation https://www.grid.ac/institutes/grid.6553.5
    83 schema:familyName Kuske
    84 schema:givenName Dietrich
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013520370123.82
    86 rdf:type schema:Person
    87 sg:person.014551676263.38 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
    88 schema:familyName Zetzsche
    89 schema:givenName Georg
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014551676263.38
    91 rdf:type schema:Person
    92 sg:pub.10.1007/3-540-60178-3_93 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040488919
    93 https://doi.org/10.1007/3-540-60178-3_93
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-1-4613-9771-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018692631
    96 https://doi.org/10.1007/978-1-4613-9771-7
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/978-3-662-44522-8_29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017435896
    99 https://doi.org/10.1007/978-3-662-44522-8_29
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/978-3-662-53132-7_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042131935
    102 https://doi.org/10.1007/978-3-662-53132-7_21
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/978-3-663-09367-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003958860
    105 https://doi.org/10.1007/978-3-663-09367-1
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/bf02573327 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040716819
    108 https://doi.org/10.1007/bf02573327
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/bfb0016249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027506737
    111 https://doi.org/10.1007/bfb0016249
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/s00224-004-1133-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1029593225
    114 https://doi.org/10.1007/s00224-004-1133-y
    115 rdf:type schema:CreativeWork
    116 https://app.dimensions.ai/details/publication/pub.1018692631 schema:CreativeWork
    117 https://doi.org/10.1016/0021-8693(91)90275-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1019146297
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1016/0304-3975(86)90028-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008217602
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1016/0304-3975(93)90230-q schema:sameAs https://app.dimensions.ai/details/publication/pub.1027432427
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1016/s0304-3975(99)00151-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047104068
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1017/cbo9781316227343.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033189390
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1080/00927870802243580 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039759685
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1142/s0218196793000135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062962050
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.4171/ggd/221 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072317089
    132 rdf:type schema:CreativeWork
    133 https://www.grid.ac/institutes/grid.464035.0 schema:alternateName Laboratoire Spécification et Vérification
    134 schema:name LSV, CNRS & ENS Cachan, Université Paris-Saclay, Cachan, France
    135 rdf:type schema:Organization
    136 https://www.grid.ac/institutes/grid.6553.5 schema:alternateName Ilmenau University of Technology
    137 schema:name Institut für Theoretische Informatik, TU Ilmenau, Ilmenau, Germany
    138 rdf:type schema:Organization
     




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


    ...