The hierarchical structure of graph searches (Q1098301)

Given a graph \({\mathcal B}\), we show the existence of a universal automaton \({\mathcal U}\) which ``searches'' \({\mathcal B}\). U is universal in the sense that any automaton which searches \({\mathcal B}\) behaves as a subautomaton of \({\mathcal U}\). Further, \({\mathcal U}\) is naturally filtered in a manner suggestive of hierarchical search depth: level 1 corresponds to simple rules for moving on \({\mathcal B}\), level 2 to ``meta-rules'', and so on. We show that if \({\mathcal M}\) is any finite state automaton which searches \({\mathcal B}\), then \({\mathcal M}\) can in fact be embedded in some finite level \({\mathcal U}_ n\) of \({\mathcal U}\). This leads naturally to a definition of ``depth'' of an arbitrary automaton which searches \({\mathcal B}\), and we give several examples of such automata with varying depth. This notion of depth is independent of the state space structure of \({\mathcal M}\). We further describe a resulting strategy for the construction of evolutionary learning systems which learn structural control hierarchies, based on our model of the universal automaton.