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 N176f26a51fd049679bd6cb04f074b481
    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 N0f5200acf3b34df195bafb9441b0248f
    11 schema:genre chapter
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N27b496d8fb9a4717bfa5bf9596602216
    15 schema:name Synchronizing Monotonic Automata
    16 schema:pagination 111-121
    17 schema:productId N575aa4249ac448bfaaedaee0293b4a20
    18 N82f4eeb4e44640748fcb98c22350f0ce
    19 Necc1897eede446499de8967d64e8205c
    20 schema:publisher Nc6ca62ce650248808afcbf64f68d1823
    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 Nf4a83ee638ee4150a6fad4d127599802
    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 N0f5200acf3b34df195bafb9441b0248f rdf:first Na5d27140247e4aedaf0f2ee4702351e4
    31 rdf:rest Nbc81975a8b7144b89fd857f87bb29450
    32 N176f26a51fd049679bd6cb04f074b481 rdf:first Nbe6046a0353e49bbada8070cc498d637
    33 rdf:rest Nb7f33692a9e34ca6a300af3eeb49414b
    34 N204fd849641f43919bf5c8edc6d4cea3 schema:familyName Fülöp
    35 schema:givenName Zoltán
    36 rdf:type schema:Person
    37 N27b496d8fb9a4717bfa5bf9596602216 schema:isbn 978-3-540-40434-7
    38 978-3-540-45007-8
    39 schema:name Developments in Language Theory
    40 rdf:type schema:Book
    41 N575aa4249ac448bfaaedaee0293b4a20 schema:name dimensions_id
    42 schema:value pub.1012248703
    43 rdf:type schema:PropertyValue
    44 N82f4eeb4e44640748fcb98c22350f0ce schema:name readcube_id
    45 schema:value 3a5b68fe807f65e456ec748652f128cf50aa570e4c97b72868c773b113788b80
    46 rdf:type schema:PropertyValue
    47 Na5d27140247e4aedaf0f2ee4702351e4 schema:familyName Ésik
    48 schema:givenName Zoltán
    49 rdf:type schema:Person
    50 Nb7f33692a9e34ca6a300af3eeb49414b rdf:first sg:person.013001640142.17
    51 rdf:rest rdf:nil
    52 Nbc81975a8b7144b89fd857f87bb29450 rdf:first N204fd849641f43919bf5c8edc6d4cea3
    53 rdf:rest rdf:nil
    54 Nbe6046a0353e49bbada8070cc498d637 schema:affiliation https://www.grid.ac/institutes/grid.412761.7
    55 schema:familyName Ananichev
    56 schema:givenName Dimitry S.
    57 rdf:type schema:Person
    58 Nc6ca62ce650248808afcbf64f68d1823 schema:location Berlin, Heidelberg
    59 schema:name Springer Berlin Heidelberg
    60 rdf:type schema:Organisation
    61 Necc1897eede446499de8967d64e8205c schema:name doi
    62 schema:value 10.1007/3-540-45007-6_8
    63 rdf:type schema:PropertyValue
    64 Nf4a83ee638ee4150a6fad4d127599802 schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    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)


    ...