|
Intelligent systems. Theory and applications, 2021, Volume 25, Issue 4, Pages 113–116
(Mi ista428)
|
|
|
|
Part 2. Mathematics and Computer Science
Estimates of the time for the automaton to establish the properties of a graph to be a tree and a pseudo-tree
A. A. Demidova Lomonosov Moscow State University
Abstract:
In this paper, we consider automata that traverse connected plane simple undirected graphs in order to establish their properties. An algorithm is presented, using which an automaton with two colors can determine whether the graph it traverses is a tree or a pseudotree, and upper bounds are determined for the number of steps that the automaton must make.
Keywords:
Automata, graphs, trees, pseudotrees.
Citation:
A. A. Demidova, “Estimates of the time for the automaton to establish the properties of a graph to be a tree and a pseudo-tree”, Intelligent systems. Theory and applications, 25:4 (2021), 113–116
Linking options:
https://www.mathnet.ru/eng/ista428 https://www.mathnet.ru/eng/ista/v25/i4/p113
|
|