Synchronizing Monotonic Automata View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

AUTHORS

Dimitry S. Ananichev , Mikhail V. Volkov

ABSTRACT

We show that if the state set Q of a synchronizing automaton \( \mathcal{A} = \left\langle {Q,\sum ,\delta } \right\rangle \) admits a linear order such that for each letter a ∈ Σ the transformation δ(_, a) of Q preserves this order, then \( \mathcal{A} \) possesses a reset word of length |Q| − 1. We also consider two natural generalizations of the notion of a reset word and provide for them results of a similar flavour. More... »

PAGES

111-121

References to SciGraph publications

  • 2001. Synchronizing Finite Automata on Eulerian Digraphs in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2001
  • Book

    TITLE

    Developments in Language Theory

    ISBN

    978-3-540-40434-7
    978-3-540-45007-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45007-6_8

    DOI

    http://dx.doi.org/10.1007/3-540-45007-6_8

    DIMENSIONS

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


    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/1702", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Cognitive Sciences", 
            "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": "Ural Federal University", 
              "id": "https://www.grid.ac/institutes/grid.412761.7", 
              "name": [
                "Department of Mathematics and Mechanics, Ural State University, 620083\u00a0Ekaterinburg, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ananichev", 
            "givenName": "Dimitry S.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Ural Federal University", 
              "id": "https://www.grid.ac/institutes/grid.412761.7", 
              "name": [
                "Department of Mathematics and Mechanics, Ural State University, 620083\u00a0Ekaterinburg, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Volkov", 
            "givenName": "Mikhail V.", 
            "id": "sg:person.013001640142.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013001640142.17"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-44683-4_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011932985", 
              "https://doi.org/10.1007/3-540-44683-4_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0219033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842216"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1051/ita/1998321-300211", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1083550556"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2003", 
        "datePublishedReg": "2003-01-01", 
        "description": "We show that if the state set Q of a synchronizing automaton \\( \\mathcal{A} = \\left\\langle {Q,\\sum ,\\delta } \\right\\rangle \\) admits a linear order such that for each letter a \u2208 \u03a3 the transformation \u03b4(_, a) of Q preserves this order, then \\( \\mathcal{A} \\) possesses a reset word of length |Q| \u2212 1. We also consider two natural generalizations of the notion of a reset word and provide for them results of a similar flavour.", 
        "editor": [
          {
            "familyName": "\u00c9sik", 
            "givenName": "Zolt\u00e1n", 
            "type": "Person"
          }, 
          {
            "familyName": "F\u00fcl\u00f6p", 
            "givenName": "Zolt\u00e1n", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45007-6_8", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.5419817", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.5358152", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-540-40434-7", 
            "978-3-540-45007-8"
          ], 
          "name": "Developments in Language Theory", 
          "type": "Book"
        }, 
        "name": "Synchronizing Monotonic Automata", 
        "pagination": "111-121", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45007-6_8"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "3a5b68fe807f65e456ec748652f128cf50aa570e4c97b72868c773b113788b80"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1012248703"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45007-6_8", 
          "https://app.dimensions.ai/details/publication/pub.1012248703"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T15:54", 
        "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_8672_00000559.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-45007-6_8"
      }
    ]
     

    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-45007-6_8'

    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-45007-6_8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45007-6_8'

    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-45007-6_8'


     

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

    90 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45007-6_8 schema:about anzsrc-for:17
    2 anzsrc-for:1702
    3 schema:author Nf11fac394a784ed2a212862870f4da3a
    4 schema:citation sg:pub.10.1007/3-540-44683-4_38
    5 https://doi.org/10.1051/ita/1998321-300211
    6 https://doi.org/10.1137/0219033
    7 schema:datePublished 2003
    8 schema:datePublishedReg 2003-01-01
    9 schema:description We show that if the state set Q of a synchronizing automaton \( \mathcal{A} = \left\langle {Q,\sum ,\delta } \right\rangle \) admits a linear order such that for each letter a ∈ Σ the transformation δ(_, a) of Q preserves this order, then \( \mathcal{A} \) possesses a reset word of length |Q| − 1. We also consider two natural generalizations of the notion of a reset word and provide for them results of a similar flavour.
    10 schema:editor N2112b7108d744ffc8bf4e8d9c93c4abf
    11 schema:genre chapter
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf Nc41d3193254446e8ad1f7bc56926c61a
    15 schema:name Synchronizing Monotonic Automata
    16 schema:pagination 111-121
    17 schema:productId N1a632c4e556a4e32adcf9150406328c9
    18 N923470da743146be914bb53f4fb11e60
    19 N92626158dfc7459ea2946ff92a02163a
    20 schema:publisher N509191131cf249e0b2a5319e938b2f38
    21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012248703
    22 https://doi.org/10.1007/3-540-45007-6_8
    23 schema:sdDatePublished 2019-04-15T15:54
    24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    25 schema:sdPublisher N7f0767b648fc4f02b4d3e345b9f94e80
    26 schema:url http://link.springer.com/10.1007/3-540-45007-6_8
    27 sgo:license sg:explorer/license/
    28 sgo:sdDataset chapters
    29 rdf:type schema:Chapter
    30 N1a632c4e556a4e32adcf9150406328c9 schema:name readcube_id
    31 schema:value 3a5b68fe807f65e456ec748652f128cf50aa570e4c97b72868c773b113788b80
    32 rdf:type schema:PropertyValue
    33 N2112b7108d744ffc8bf4e8d9c93c4abf rdf:first Nbc81a4e0d3d74f698eade406e97ef8c4
    34 rdf:rest N74cd355453e748d4abbb344853131ac4
    35 N41010fa37359457bb832585063a27453 rdf:first sg:person.013001640142.17
    36 rdf:rest rdf:nil
    37 N47ba1a0d7d464319be7f2f7d7e1333ec schema:familyName Fülöp
    38 schema:givenName Zoltán
    39 rdf:type schema:Person
    40 N509191131cf249e0b2a5319e938b2f38 schema:location Berlin, Heidelberg
    41 schema:name Springer Berlin Heidelberg
    42 rdf:type schema:Organisation
    43 N74cd355453e748d4abbb344853131ac4 rdf:first N47ba1a0d7d464319be7f2f7d7e1333ec
    44 rdf:rest rdf:nil
    45 N7f0767b648fc4f02b4d3e345b9f94e80 schema:name Springer Nature - SN SciGraph project
    46 rdf:type schema:Organization
    47 N923470da743146be914bb53f4fb11e60 schema:name dimensions_id
    48 schema:value pub.1012248703
    49 rdf:type schema:PropertyValue
    50 N92626158dfc7459ea2946ff92a02163a schema:name doi
    51 schema:value 10.1007/3-540-45007-6_8
    52 rdf:type schema:PropertyValue
    53 Nbc81a4e0d3d74f698eade406e97ef8c4 schema:familyName Ésik
    54 schema:givenName Zoltán
    55 rdf:type schema:Person
    56 Nc41d3193254446e8ad1f7bc56926c61a schema:isbn 978-3-540-40434-7
    57 978-3-540-45007-8
    58 schema:name Developments in Language Theory
    59 rdf:type schema:Book
    60 Nd6971757835c4207989cb94618bcd868 schema:affiliation https://www.grid.ac/institutes/grid.412761.7
    61 schema:familyName Ananichev
    62 schema:givenName Dimitry S.
    63 rdf:type schema:Person
    64 Nf11fac394a784ed2a212862870f4da3a rdf:first Nd6971757835c4207989cb94618bcd868
    65 rdf:rest N41010fa37359457bb832585063a27453
    66 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Psychology and Cognitive Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Cognitive Sciences
    71 rdf:type schema:DefinedTerm
    72 sg:grant.5358152 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-45007-6_8
    73 rdf:type schema:MonetaryGrant
    74 sg:grant.5419817 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-45007-6_8
    75 rdf:type schema:MonetaryGrant
    76 sg:person.013001640142.17 schema:affiliation https://www.grid.ac/institutes/grid.412761.7
    77 schema:familyName Volkov
    78 schema:givenName Mikhail V.
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013001640142.17
    80 rdf:type schema:Person
    81 sg:pub.10.1007/3-540-44683-4_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011932985
    82 https://doi.org/10.1007/3-540-44683-4_38
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1051/ita/1998321-300211 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083550556
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1137/0219033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842216
    87 rdf:type schema:CreativeWork
    88 https://www.grid.ac/institutes/grid.412761.7 schema:alternateName Ural Federal University
    89 schema:name Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russia
    90 rdf:type schema:Organization
     




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


    ...