2017-12
AUTHORSMartin Huschenbett, Dietrich Kuske, Georg Zetzsche
ABSTRACTWe 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... »
PAGES475-508
http://scigraph.springernature.com/pub.10.1007/s00233-016-9835-4
DOIhttp://dx.doi.org/10.1007/s00233-016-9835-4
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1040754113
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
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