Abstrakt. En ändlig automaton, helt enkelt kallad robot, måste utforska en graf, det vill säga besöka alla noder i grafen. Roboten har ingen förkunskaper om grafens topologi eller dess storlek. Det är känt att för alla k-state robot, det finns en graf av maximal grad 3 som roboten inte kan utforska. Denna artikel behandlar effekterna av att tillåta systemdesignern att lägga till korta etiketter till grafnoder i ett förbearbetningsskede, för att hjälpa prospektering av roboten. Vi beskriver en prospekteringsalgoritm som, med tanke på lämpliga 2-bitarsetiketter (i själva verket endast 3-värderade etiketter), gör det möjligt för en robot att utforska alla grafer. Dessutom beskriver vi en lämplig märkningsalgoritm för att generera R. Cohen stöds av Pacific Theaters Foundation. P. Fraigniaud stöddes av projektet "PairAPair" av ACI Masses de Données, projektet "Fragile" av ACI Sécurité et Informatique och projektet "Grand Large" av INRIA. A. Korman stöddes delvis av projektet "GANG" i INRIA. D. Peleg fick delvis stöd av ett anslag från Israels vetenskapsstiftelse. Författarnas adresser: R. Cohen, Institutionen för el- och datateknik, Boston University, Boston, MA, e-post: cohenr@bu.edu; P. Fraigniaud, CNRS och Université Paris Diderot - Paris 7, Frankrike, e-post: pierre@liafa.jussieu.fr; D. Ilcinkas, CNRS och Université Bordeaux I, Frankrike, e-post: david.ilcinkas@ labri.fr; A. Korman, CNRS och Université Paris Diderot - Paris 7, Frankrike, e-post: amos.korman@liafa.jussieu.fr; D. Peleg, Institutionen för datavetenskap, Weizmann Institute, Rehovot, Israel, e-post: david.peleg@weizmann.ac.il. Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller direkt kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Tillstånd kan begäras från Publications Department., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (kräver etiketter i linjär tid. Vi visar också hur vi kan ändra vårt märkningssystem så att en robot kan utforska alla grafer av begränsad grad, givet lämpliga 1-bitars etiketter. Med andra ord, även om det inte finns någon robot som kan utforska alla grafer av maximal grad 3, finns det en robot R, och ett sätt att färga i svart eller vitt noderna av någon begränsad grad graf G, så att R kan utforska den färgade grafen G. Slutligen ger vi omöjliga resultat när det gäller graf prospektering av en robot utan inre minne (d.v.s. en en-state automaton).
Det bevisas i REF att det finns en algoritm färgning noderna med bara tre färger, och en ändlig automaton med denna färg som kan utforska alla grafer.
Label-guided graph exploration by a finite automaton
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}