A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-12

AUTHORS

Christian Choffrut, Štěpán Holub

ABSTRACT

An endomorphism of the free monoid A∗ is invertible if it is injective and extends to an automorphism of the free group generated by A. A simple example: the endomorphism that leaves all generators A invariant except one, say a, which is mapped to ba for some other generator b. We give a monoid presentation for the submonoid generated by all such endomorphisms when a and b are taken arbitrarily. These left translations are a special case of Nielsen positive transformations: “left” because the mutiplicative constant acts on the left and “positive” because this constant belongs to the free monoid, not the free group. More... »

PAGES

444-458

References to SciGraph publications

  • 1999-10. Some remarks on invertible substitutions on three letter alphabet in SCIENCE BULLETIN
  • 1983-03. Topology of finite graphs in INVENTIONES MATHEMATICAE
  • 1924-09. Die Isomorphismengruppe der freien Gruppen in MATHEMATISCHE ANNALEN
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00233-015-9737-x

    DOI

    http://dx.doi.org/10.1007/s00233-015-9737-x

    DIMENSIONS

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


    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/1701", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology and Cognitive Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Laboratoire d'Informatique Algorithmique: Fondements et Applications", 
              "id": "https://www.grid.ac/institutes/grid.462842.e", 
              "name": [
                "LIAFA, CNRS and Universit\u00e9 Paris 7 Denis Diderot, Paris Cedex 13, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Choffrut", 
            "givenName": "Christian", 
            "id": "sg:person.016123107772.18", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016123107772.18"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Charles University", 
              "id": "https://www.grid.ac/institutes/grid.4491.8", 
              "name": [
                "Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Holub", 
            "givenName": "\u0160t\u011bp\u00e1n", 
            "id": "sg:person.015137452373.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015137452373.93"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1090/s0894-0347-03-00440-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001605756"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(01)00207-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011701272"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(02)00726-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015516213"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01556078", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022509734", 
              "https://doi.org/10.1007/bf01556078"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2014.12.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024034087"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02095993", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027472254", 
              "https://doi.org/10.1007/bf02095993"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02095993", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027472254", 
              "https://doi.org/10.1007/bf02095993"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1112/jlms/s2-8.2.259", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028402231"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(91)90383-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028679981"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02886152", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034997641", 
              "https://doi.org/10.1007/bf02886152"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02886152", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034997641", 
              "https://doi.org/10.1007/bf02886152"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0196-8858(03)00102-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035992003"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1515/9783111544526", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041596228"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-4049(84)90062-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043473819"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781107326019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098682766"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-12", 
        "datePublishedReg": "2016-12-01", 
        "description": "An endomorphism of the free monoid A\u2217 is invertible if it is injective and extends to an automorphism of the free group generated by A. A simple example: the endomorphism that leaves all generators A invariant except one, say a, which is mapped to ba for some other generator b. We give a monoid presentation for the submonoid generated by all such endomorphisms when a and b are taken arbitrarily. These left translations are a special case of Nielsen positive transformations: \u201cleft\u201d because the mutiplicative constant acts on the left and \u201cpositive\u201d because this constant belongs to the free monoid, not the free group.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00233-015-9737-x", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.6874817", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136094", 
            "issn": [
              "0037-1912", 
              "1432-2137"
            ], 
            "name": "Semigroup Forum", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "93"
          }
        ], 
        "name": "A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid", 
        "pagination": "444-458", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "ab0ea0f854950f15c373ee7af065fe59a662afb496c9bf612115e0f9c280102a"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00233-015-9737-x"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1035908640"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00233-015-9737-x", 
          "https://app.dimensions.ai/details/publication/pub.1035908640"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T14:04", 
        "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_8660_00000489.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00233-015-9737-x"
      }
    ]
     

    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-015-9737-x'

    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-015-9737-x'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00233-015-9737-x'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00233-015-9737-x'


     

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

    115 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00233-015-9737-x schema:about anzsrc-for:17
    2 anzsrc-for:1701
    3 schema:author N6db6ef13e8814abfb37cb1746f0c85ba
    4 schema:citation sg:pub.10.1007/bf01556078
    5 sg:pub.10.1007/bf02095993
    6 sg:pub.10.1007/bf02886152
    7 https://doi.org/10.1016/0022-4049(84)90062-8
    8 https://doi.org/10.1016/0304-3975(91)90383-d
    9 https://doi.org/10.1016/j.disc.2014.12.010
    10 https://doi.org/10.1016/s0196-8858(03)00102-7
    11 https://doi.org/10.1016/s0304-3975(01)00207-9
    12 https://doi.org/10.1016/s0304-3975(02)00726-0
    13 https://doi.org/10.1017/cbo9781107326019
    14 https://doi.org/10.1090/s0894-0347-03-00440-5
    15 https://doi.org/10.1112/jlms/s2-8.2.259
    16 https://doi.org/10.1515/9783111544526
    17 schema:datePublished 2016-12
    18 schema:datePublishedReg 2016-12-01
    19 schema:description An endomorphism of the free monoid A∗ is invertible if it is injective and extends to an automorphism of the free group generated by A. A simple example: the endomorphism that leaves all generators A invariant except one, say a, which is mapped to ba for some other generator b. We give a monoid presentation for the submonoid generated by all such endomorphisms when a and b are taken arbitrarily. These left translations are a special case of Nielsen positive transformations: “left” because the mutiplicative constant acts on the left and “positive” because this constant belongs to the free monoid, not the free group.
    20 schema:genre research_article
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N3353adebcba84f128257c5233e55a8e3
    24 Nf2a0a5d02ec94adb8010caf969541bbe
    25 sg:journal.1136094
    26 schema:name A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid
    27 schema:pagination 444-458
    28 schema:productId N2023bde7be2541d0a32f791594066292
    29 N5978026728b44f1c8de4d4a20480746b
    30 Nfcc38be0c24f4aba99bc495cf4492731
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035908640
    32 https://doi.org/10.1007/s00233-015-9737-x
    33 schema:sdDatePublished 2019-04-10T14:04
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N3c796d1da4004e219a99a43efe8d8f25
    36 schema:url http://link.springer.com/10.1007/s00233-015-9737-x
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset articles
    39 rdf:type schema:ScholarlyArticle
    40 N2023bde7be2541d0a32f791594066292 schema:name dimensions_id
    41 schema:value pub.1035908640
    42 rdf:type schema:PropertyValue
    43 N3353adebcba84f128257c5233e55a8e3 schema:issueNumber 3
    44 rdf:type schema:PublicationIssue
    45 N3c796d1da4004e219a99a43efe8d8f25 schema:name Springer Nature - SN SciGraph project
    46 rdf:type schema:Organization
    47 N3fbae2cf925840dbac7c020b07c8f9ec rdf:first sg:person.015137452373.93
    48 rdf:rest rdf:nil
    49 N5978026728b44f1c8de4d4a20480746b schema:name doi
    50 schema:value 10.1007/s00233-015-9737-x
    51 rdf:type schema:PropertyValue
    52 N6db6ef13e8814abfb37cb1746f0c85ba rdf:first sg:person.016123107772.18
    53 rdf:rest N3fbae2cf925840dbac7c020b07c8f9ec
    54 Nf2a0a5d02ec94adb8010caf969541bbe schema:volumeNumber 93
    55 rdf:type schema:PublicationVolume
    56 Nfcc38be0c24f4aba99bc495cf4492731 schema:name readcube_id
    57 schema:value ab0ea0f854950f15c373ee7af065fe59a662afb496c9bf612115e0f9c280102a
    58 rdf:type schema:PropertyValue
    59 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Psychology and Cognitive Sciences
    61 rdf:type schema:DefinedTerm
    62 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Psychology
    64 rdf:type schema:DefinedTerm
    65 sg:grant.6874817 http://pending.schema.org/fundedItem sg:pub.10.1007/s00233-015-9737-x
    66 rdf:type schema:MonetaryGrant
    67 sg:journal.1136094 schema:issn 0037-1912
    68 1432-2137
    69 schema:name Semigroup Forum
    70 rdf:type schema:Periodical
    71 sg:person.015137452373.93 schema:affiliation https://www.grid.ac/institutes/grid.4491.8
    72 schema:familyName Holub
    73 schema:givenName Štěpán
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015137452373.93
    75 rdf:type schema:Person
    76 sg:person.016123107772.18 schema:affiliation https://www.grid.ac/institutes/grid.462842.e
    77 schema:familyName Choffrut
    78 schema:givenName Christian
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016123107772.18
    80 rdf:type schema:Person
    81 sg:pub.10.1007/bf01556078 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022509734
    82 https://doi.org/10.1007/bf01556078
    83 rdf:type schema:CreativeWork
    84 sg:pub.10.1007/bf02095993 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027472254
    85 https://doi.org/10.1007/bf02095993
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/bf02886152 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034997641
    88 https://doi.org/10.1007/bf02886152
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/0022-4049(84)90062-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043473819
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1016/0304-3975(91)90383-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1028679981
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/j.disc.2014.12.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024034087
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/s0196-8858(03)00102-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035992003
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/s0304-3975(01)00207-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011701272
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/s0304-3975(02)00726-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015516213
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1017/cbo9781107326019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098682766
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1090/s0894-0347-03-00440-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001605756
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1112/jlms/s2-8.2.259 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028402231
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1515/9783111544526 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041596228
    109 rdf:type schema:CreativeWork
    110 https://www.grid.ac/institutes/grid.4491.8 schema:alternateName Charles University
    111 schema:name Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
    112 rdf:type schema:Organization
    113 https://www.grid.ac/institutes/grid.462842.e schema:alternateName Laboratoire d'Informatique Algorithmique: Fondements et Applications
    114 schema:name LIAFA, CNRS and Université Paris 7 Denis Diderot, Paris Cedex 13, France
    115 rdf:type schema:Organization
     




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


    ...