Abstrakt. Under robotmodellen, visar vi att en robot behöver en log d) bitar av minne för att utföra utforskning av digrafer med n noder och maximal ut-grad d. Vi beskriver sedan en algoritm som tillåter utforskning av någon n-node digraph med maximal ut-grad d att utföras av en robot med ett minne av storlek O (nd log n) bitar. Enligt agentmodellen visar vi att utforskning inte kan åstadkommas av en agent utan minne. Vi beskriver sedan en prospekteringsalgoritm för en agent med ett konstant storleksminne, med hjälp av en whiteboard av storlek O(log d) bitar vid varje nod av ut-grad d.
Till exempel visas det i REF att prospektering med stopp av n-node träd kräver en robot med minnesstorlek  och att prospektering med återkomst av n-node träd kan uppnås av en robot med O(log 2 n) minne bitar.
Tree exploration with little memory
{'venue': 'Journal of Algorithms', 'journal': None, 'mag_field_of_study': ['Computer Science']}