Label-Guided Graph Exploration by a Finite Automaton View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Reuven Cohen , Pierre Fraigniaud , David Ilcinkas , Amos Korman , David Peleg

ABSTRACT

A finite automaton, simply referred to as a robot, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It is known that, for any k-state robot, there exists a (k+1)-node graph of maximum degree 3 that the robot cannot explore. This paper considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, and using these labels to guide the exploration by the robot. We describe an exploration algorithm that given appropriate 2-bit labels (in fact, only 3-valued labels) allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels, in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot , and a way to color in black or white the nodes of any bounded-degree graph G, so that can explore the colored graph G. Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single state automaton). More... »

PAGES

335-346

References to SciGraph publications

  • 2004. Graph Exploration by a Finite Automaton in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004
  • 1979. Automaten in planaren graphen in THEORETICAL COMPUTER SCIENCE 4TH GI CONFERENCE
  • Book

    TITLE

    Automata, Languages and Programming

    ISBN

    978-3-540-27580-0
    978-3-540-31691-6

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11523468_28

    DOI

    http://dx.doi.org/10.1007/11523468_28

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Weizmann Institute of Science", 
              "id": "https://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Dept. of Computer Science, Weizmann Institute, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cohen", 
            "givenName": "Reuven", 
            "id": "sg:person.013647657237.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013647657237.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French National Centre for Scientific Research", 
              "id": "https://www.grid.ac/institutes/grid.4444.0", 
              "name": [
                "CNRS, LRI, Universit\u00e9 Paris-Sud, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fraigniaud", 
            "givenName": "Pierre", 
            "id": "sg:person.013424402135.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French National Centre for Scientific Research", 
              "id": "https://www.grid.ac/institutes/grid.4444.0", 
              "name": [
                "CNRS, LRI, Universit\u00e9 Paris-Sud, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ilcinkas", 
            "givenName": "David", 
            "id": "sg:person.010032333055.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010032333055.75"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Weizmann Institute of Science", 
              "id": "https://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Dept. of Computer Science, Weizmann Institute, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Korman", 
            "givenName": "Amos", 
            "id": "sg:person.013353220506.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Weizmann Institute of Science", 
              "id": "https://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Dept. of Computer Science, Weizmann Institute, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Peleg", 
            "givenName": "David", 
            "id": "sg:person.012357743251.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357743251.05"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/mana.19780860120", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001418618"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28629-5_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022544006", 
              "https://doi.org/10.1007/978-3-540-28629-5_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28629-5_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022544006", 
              "https://doi.org/10.1007/978-3-540-28629-5_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-09118-1_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028339951", 
              "https://doi.org/10.1007/3-540-09118-1_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1978.30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086207665"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005", 
        "datePublishedReg": "2005-01-01", 
        "description": "A finite automaton, simply referred to as a robot, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It is known that, for any k-state robot, there exists a (k+1)-node graph of maximum degree 3 that the robot cannot explore. This paper considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, and using these labels to guide the exploration by the robot. We describe an exploration algorithm that given appropriate 2-bit labels (in fact, only 3-valued labels) allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels, in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot , and a way to color in black or white the nodes of any bounded-degree graph G, so that can explore the colored graph G. Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single state automaton).", 
        "editor": [
          {
            "familyName": "Caires", 
            "givenName": "Lu\u00eds", 
            "type": "Person"
          }, 
          {
            "familyName": "Italiano", 
            "givenName": "Giuseppe F.", 
            "type": "Person"
          }, 
          {
            "familyName": "Monteiro", 
            "givenName": "Lu\u00eds", 
            "type": "Person"
          }, 
          {
            "familyName": "Palamidessi", 
            "givenName": "Catuscia", 
            "type": "Person"
          }, 
          {
            "familyName": "Yung", 
            "givenName": "Moti", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11523468_28", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-27580-0", 
            "978-3-540-31691-6"
          ], 
          "name": "Automata, Languages and Programming", 
          "type": "Book"
        }, 
        "name": "Label-Guided Graph Exploration by a Finite Automaton", 
        "pagination": "335-346", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1040407045"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11523468_28"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c07b1c2700f75e9e5942d8ae50c82565cdcd2c911b8925fc8c4d33e8b97ad9aa"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11523468_28", 
          "https://app.dimensions.ai/details/publication/pub.1040407045"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08: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/0000000359_0000000359/records_29215_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11523468_28"
      }
    ]
     

    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/11523468_28'

    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/11523468_28'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11523468_28'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11523468_28'


     

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

    130 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11523468_28 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N900993941a064b4b96ef0e7ed7e02bc8
    4 schema:citation sg:pub.10.1007/3-540-09118-1_28
    5 sg:pub.10.1007/978-3-540-28629-5_34
    6 https://doi.org/10.1002/mana.19780860120
    7 https://doi.org/10.1109/sfcs.1978.30
    8 schema:datePublished 2005
    9 schema:datePublishedReg 2005-01-01
    10 schema:description A finite automaton, simply referred to as a robot, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It is known that, for any k-state robot, there exists a (k+1)-node graph of maximum degree 3 that the robot cannot explore. This paper considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, and using these labels to guide the exploration by the robot. We describe an exploration algorithm that given appropriate 2-bit labels (in fact, only 3-valued labels) allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels, in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot , and a way to color in black or white the nodes of any bounded-degree graph G, so that can explore the colored graph G. Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single state automaton).
    11 schema:editor Nd4e6e2c05969407fad9159ab4fbc096c
    12 schema:genre chapter
    13 schema:inLanguage en
    14 schema:isAccessibleForFree true
    15 schema:isPartOf N62d96dca44df4d1998cae9a9fad7ffca
    16 schema:name Label-Guided Graph Exploration by a Finite Automaton
    17 schema:pagination 335-346
    18 schema:productId N13d028f6d6264c3cbfdd8e7ba4ec146b
    19 N379505c413964a5a98de8491f738d3c8
    20 N97159173554c4173bb82db67408a3546
    21 schema:publisher N249283d86a084d66926c17f3493d660f
    22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040407045
    23 https://doi.org/10.1007/11523468_28
    24 schema:sdDatePublished 2019-04-16T08:04
    25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    26 schema:sdPublisher Nc7ad0fa541414db5ba638c68b80a1cdc
    27 schema:url https://link.springer.com/10.1007%2F11523468_28
    28 sgo:license sg:explorer/license/
    29 sgo:sdDataset chapters
    30 rdf:type schema:Chapter
    31 N13d028f6d6264c3cbfdd8e7ba4ec146b schema:name doi
    32 schema:value 10.1007/11523468_28
    33 rdf:type schema:PropertyValue
    34 N249283d86a084d66926c17f3493d660f schema:location Berlin, Heidelberg
    35 schema:name Springer Berlin Heidelberg
    36 rdf:type schema:Organisation
    37 N2584dec041554eed8764db55c0f5f458 rdf:first N6e60e9bf96ef4eae95a3e00a8b931b5c
    38 rdf:rest Nc2d7b871bc644356850da75de5e35ec0
    39 N2b723a1b9fe34926a25219aa82525cfc schema:familyName Yung
    40 schema:givenName Moti
    41 rdf:type schema:Person
    42 N3597d659250e446db097ced5da592c43 schema:familyName Monteiro
    43 schema:givenName Luís
    44 rdf:type schema:Person
    45 N360694b97445442690d982b2cfdf1461 rdf:first sg:person.010032333055.75
    46 rdf:rest Nd335ee1045204865a44e7da5d3305b91
    47 N379505c413964a5a98de8491f738d3c8 schema:name dimensions_id
    48 schema:value pub.1040407045
    49 rdf:type schema:PropertyValue
    50 N37ea2adc1dcc47fba48dc47c4fe251fc rdf:first N2b723a1b9fe34926a25219aa82525cfc
    51 rdf:rest rdf:nil
    52 N62d96dca44df4d1998cae9a9fad7ffca schema:isbn 978-3-540-27580-0
    53 978-3-540-31691-6
    54 schema:name Automata, Languages and Programming
    55 rdf:type schema:Book
    56 N6e60e9bf96ef4eae95a3e00a8b931b5c schema:familyName Italiano
    57 schema:givenName Giuseppe F.
    58 rdf:type schema:Person
    59 N7712c03538374adda069680afe08ccfd schema:familyName Caires
    60 schema:givenName Luís
    61 rdf:type schema:Person
    62 N8a38914dd792495caa90b8e43a5d52e2 schema:familyName Palamidessi
    63 schema:givenName Catuscia
    64 rdf:type schema:Person
    65 N8ecddd8bee144aecbae0205bfdcbff13 rdf:first sg:person.013424402135.28
    66 rdf:rest N360694b97445442690d982b2cfdf1461
    67 N900993941a064b4b96ef0e7ed7e02bc8 rdf:first sg:person.013647657237.68
    68 rdf:rest N8ecddd8bee144aecbae0205bfdcbff13
    69 N91f85a92c4ac459580548c8f65c61865 rdf:first N8a38914dd792495caa90b8e43a5d52e2
    70 rdf:rest N37ea2adc1dcc47fba48dc47c4fe251fc
    71 N97159173554c4173bb82db67408a3546 schema:name readcube_id
    72 schema:value c07b1c2700f75e9e5942d8ae50c82565cdcd2c911b8925fc8c4d33e8b97ad9aa
    73 rdf:type schema:PropertyValue
    74 Nc2d7b871bc644356850da75de5e35ec0 rdf:first N3597d659250e446db097ced5da592c43
    75 rdf:rest N91f85a92c4ac459580548c8f65c61865
    76 Nc7ad0fa541414db5ba638c68b80a1cdc schema:name Springer Nature - SN SciGraph project
    77 rdf:type schema:Organization
    78 Nd335ee1045204865a44e7da5d3305b91 rdf:first sg:person.013353220506.00
    79 rdf:rest Nfd59b6c492b14d77b19b8a22fc808719
    80 Nd4e6e2c05969407fad9159ab4fbc096c rdf:first N7712c03538374adda069680afe08ccfd
    81 rdf:rest N2584dec041554eed8764db55c0f5f458
    82 Nfd59b6c492b14d77b19b8a22fc808719 rdf:first sg:person.012357743251.05
    83 rdf:rest rdf:nil
    84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Information and Computing Sciences
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Artificial Intelligence and Image Processing
    89 rdf:type schema:DefinedTerm
    90 sg:person.010032333055.75 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
    91 schema:familyName Ilcinkas
    92 schema:givenName David
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010032333055.75
    94 rdf:type schema:Person
    95 sg:person.012357743251.05 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
    96 schema:familyName Peleg
    97 schema:givenName David
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357743251.05
    99 rdf:type schema:Person
    100 sg:person.013353220506.00 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
    101 schema:familyName Korman
    102 schema:givenName Amos
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00
    104 rdf:type schema:Person
    105 sg:person.013424402135.28 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
    106 schema:familyName Fraigniaud
    107 schema:givenName Pierre
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28
    109 rdf:type schema:Person
    110 sg:person.013647657237.68 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
    111 schema:familyName Cohen
    112 schema:givenName Reuven
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013647657237.68
    114 rdf:type schema:Person
    115 sg:pub.10.1007/3-540-09118-1_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028339951
    116 https://doi.org/10.1007/3-540-09118-1_28
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-540-28629-5_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022544006
    119 https://doi.org/10.1007/978-3-540-28629-5_34
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1002/mana.19780860120 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001418618
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1109/sfcs.1978.30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086207665
    124 rdf:type schema:CreativeWork
    125 https://www.grid.ac/institutes/grid.13992.30 schema:alternateName Weizmann Institute of Science
    126 schema:name Dept. of Computer Science, Weizmann Institute, Israel
    127 rdf:type schema:Organization
    128 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
    129 schema:name CNRS, LRI, Université Paris-Sud, France
    130 rdf:type schema:Organization
     




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


    ...